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

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

有许多构建corecursive数据的例子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)哪个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的答案.

概括示例

这里所有的三个实施例是本质上变换成corecursive流递归函数,即,它们具有一些初始状态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- fix在允许递归let表达式的语言中不必要的规则的特定情况)来编写..

非流式示例

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

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))

这就是我们想要的.

Answer 3

Fibonacci序列,例如:

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