在非函数类型上“修复”的有用实例化？

Question

每次我用fix :: (a -> a) -> a，都是

类型

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

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

Answer 1

我不知道你是否认为这个例子很简单，但你可以直接使用 fix（不通过函数）来构建数据：

repeat :: a -> [a]
repeat x = fix (x:)

Answer 2

斐波那契数列，例如：

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].

Answer 3

有很多使用 fix 构建核心递归数据的示例。我不太了解一般理论，但似乎任何像流的数据类型，因为到目前为止，你总是可以输出一个给定流的值，可以用 fix 没有给它一个函数类型。

示例

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

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) 对，其中 f 是第 n 个阶乘数 -

可以最容易地生成阶乘数

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

如果我们将 (n,f) 到 (n+1, f*(n+1)) 对，然后将 (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 而不是 fix - - 在允许递归 let 表达式的语言中 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))

这就是我们想要的。

在非函数类型上“修复”的有用实例化？

Useful instantiations of “fix” on non-function types?

recursion

haskell

fixpoint-combinators

示例

概括示例

非流示例