list - 在haskell中创建循环列表的三种方法

Question

我对 Haskell 中的循环/无限列表感兴趣。我读到了 让..in 声明和 哪里条款，我觉得它们有重要的作用，但我仍然不明白。

具体来说，我已经为交替的 0 和 1 的无限列表编写了三个版本的代码。我认为这就是 Haskell 中循环列表的含义。

cyclic = let x = 0 : y 
             y = 1 : x
         in x

cyclic' = [0,1] ++ cyclic'

cyclic'' = [0,1] ++ x
    where x = cyclic''

第二个对我来说似乎最简单、最短和最自然，但这可能是因为我仍然不完全适应 let..in 和 while。

这三个列表是否以相同的方式表示？

Answer 1

我想提一个重要的区别:

cyclic' = [0,1] ++ cyclic'

cyclic'' = [0,1] ++ x
    where x = cyclic''

这两个函数是递归的 从某种意义上说，函数的定义引用了自身。但

cyclic = let x = 0 : y 
             y = 1 : x
         in x

不是! 它使用 x在内部，这是递归的，但整个 cyclic不是 - 在它的定义中没有提到它自己。这也是编译成核心语言时它们不同的原因。

这具有一些重要的实际意义，即递归函数不能是 inlined ，但非递归可以。这就是为什么你经常看到这样的定义

fix :: (a -> a) -> a
fix f = let x = f x in x

(来自 Data.Function 的 source )而不是更直接

fix f = f (fix f)

(我不确定为什么 GHC 不会自动执行此操作。)

为了完整起见，还有其他简短的方法来定义 cyclic :

-- recursive:
cyclic = 0 : 1 : cyclic
-- non-recursive:
cyclic = let x = 0 : 1 : x in x
cyclic = cycle [0,1]
cyclic = fix ([0,1] ++)

更新:举个例子:让我们定义

-- The `const` combinator, defined explicitly so that
-- it gets inlined.
k :: a -> b -> a
k x y = x

fix, fix' :: (a -> a) -> a
fix f     = let x = f x in x
fix' f    = f (fix' f)

main = do
    print $ fix (k 1)
    print $ fix' (k 2)

所以fix'是递归的，而 fix不是( fix 的定义是从 Data.Function 复制的)。当我们使用 fix' 时会发生什么?编译器不能内联它，因为内联后，它会得到一个包含 fix' 的表达式。再次。它应该第二次内联它吗？然后第三次？因此，递归函数永远不会被设计内联。另一方面，fix不是递归的，所以 fix (k 1)被内联到 let x = k 1 x in x .然后编译器内联 k ，结果是 let x = 1 in x ，它被简单地替换为 1 .

我们可以通过转储核心语言中的编译代码来验证上述主张:

$ ghc -ddump-simpl  -dsuppress-all Main.hs 
[1 of 1] Compiling Main             ( Main.hs, Main.o )

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 24, types: 27, coercions: 0}

Rec {
fix'_reJ
fix'_reJ = \ @ a_c f_aeR -> f_aeR (fix'_reJ f_aeR)
end Rec }

main
main =
  >>
    $fMonadIO
    ($ (print $fShowInteger) (__integer 1))
    ($ (print $fShowInteger)
       (fix'_reJ
          (let {
             x_aeN
             x_aeN = __integer 2 } in
           \ _ -> x_aeN)))

main
main = runMainIO main