10

每次我用过fix :: (a -> a) -> a，它一直在类型

((a -> b) -> a -> b) -> a -> b

对于一些a和b。实际上是否有一些应用程序的fix类型参数没有实例化为函数类型，而不是像这样的微不足道的东西fix (const 0)？将签名保留最一般的目的是什么？

4

3 回答 3

10

我不知道你是否会认为这个例子是微不足道的，但你可以fix直接使用（无需通过函数）来构建数据：

repeat :: a -> [a]
repeat x = fix (x:)
于 2015-01-20T01:57:31.100 回答
8

有很多使用fix. 我没有足够的知识来详细阐述一般理论，但似乎任何类似于流的数据类型，因为到目前为止，你总是可以在给定流的情况下再输出一个值，可以在fix不给它喂食的情况下计算函数类型。

例子

最简单的例子（在 Cactus 的回答中给出）是一个重复的值流，例如

x = [1, 1, 1, 1, 1, 1, 1, 1, ...]

这满足方程

(1:) x = x

并且可以由

>> fix (1:)
[1,1,1,1,1,1,1,1,1,1,...]

一个稍微复杂一点的例子是自然数

n = [0, 1, 2, 3, 4, 5, 6, ...]

满足方程

0 : map (+1) n = n

并且可以由

>> fix ((0:) . map (+1))
[0,1,2,3,4,5,6,7,8,9,...]

(n,f)如果我们查看第 th 个阶乘数的对，f则可以最容易地生成n阶乘数 -

x = [(0,1), (1,1), (2,2), (3,6), (4,24), (5,120), ...]

如果我们将这对(n,f)带到(n+1, f*(n+1))然后将 cons(0,1)带到列表的开头，这是固定的。所以它们可以由

>> fix $ \xs -> (0,1) : map (\(n,f) -> (n+1,f*(n+1))) xs
[(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720),(7,5040),...]

可以类似地生成斐波那契数，如 user3237465 的答案。

概括例子

这里的所有三个示例本质上都是转换为核心递归流的递归函数，即它们具有一些初始状态s，并且流发出的值是s，f s，f (f s)等等f。这样做的一般方法是函数iterate

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

可以定义为fix-

iterate f x = x : map f (iterate f x)
            = (x:) . (map f) $ iterate f x
            = fix ((x:) . map f)

因此，任何重复将函数应用于某个状态的流都可以用以下形式编写fix（当然，您可以简单地使用iterate而不是——在允许递归 let 表达式的语言中不需要fix的规则的特殊情况） fix.

非流媒体示例

对于不是流的示例，请考虑在分支处具有值的二叉树 -

data Tree a = Tip | Bin a (Tree a) (Tree a) deriving (Show)

如果我们想要一棵二叉树，其节点以广度一阶标记，请注意，我们可以通过获取自身的两个副本并将左右分支中的所有值增加适当的数量来修复这样的树，如由以下函数定义 -

fun :: (Num a) => Tree a -> Tree a
fun t = Bin 1 (incr 1 t) (incr 2 t)
  where
    incr n (Bin a l r) = Bin (a+n) (incr m l) (incr m r)
      where
        m = 2 * n

使用一个简单的函数takeLevels来显示树的初始部分，然后我们将不动点计算为

>> takeLevels 3 $ fix fun
Bin 1 (Bin 2 (Bin 4 Tip Tip) (Bin 5 Tip Tip)) (Bin 3 (Bin 6 Tip Tip) (Bin 7 Tip Tip))

这就是我们想要的。

于 2015-01-20T11:00:38.273 回答
5

斐波那契数列，例如：

fibs = fix ((1:) . (1:) . (zipWith (+) <*> tail))

或forever功能：

forever x = fix (x >>)

或者斐波那契数列的另一种变体：

fibs :: State (Int, Int) [Int]
fibs = fix $ \loop -> do
    (x, y) <- get
    put (y, y + x)
    (x :) <$> loop

main = print $ take 15 $ fst $ runState fibs (1, 1)

打印[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]。

于 2015-01-20T02:49:11.570 回答