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

Question

我对 Haskell 中的循环/无限列表感兴趣。我读到了let..in语句和where子句，我觉得它们可以发挥重要作用，但我仍然不明白。

具体来说，我已经为交替的 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 不太满意。

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

score 9 · Accepted Answer

我想提一个重要的区别：

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

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

这两个函数在函数的定义引用自身的意义上是递归的。但

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

不是！它在x内部使用，这是递归的，但整体cyclic不是 - 在它的定义中没有对自身的引用。这也是为什么它们在编译成核心语言时会有所不同的原因。

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

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

（来自的来源）Data.Function而不是更直接

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

score 2 · Accepted Answer

您可以通过编译自己轻松地检查这一点-fext-core，这将为您的每个源文件编写一个相应.hrc的文件，其中包含 Haskell 的中间“核心语言”。在这种情况下，如果我们编译这段代码，我们会得到相当难以阅读的代码：

%module main:Main

  %rec
  {main:Main.cycliczqzq :: ghczmprim:GHCziTypes.ZMZN
                           ghczmprim:GHCziTypes.Int =
     base:GHCziBase.zpzp @ ghczmprim:GHCziTypes.Int
     (ghczmprim:GHCziTypes.ZC @ ghczmprim:GHCziTypes.Int
      (ghczmprim:GHCziTypes.Izh (0::ghczmprim:GHCziPrim.Intzh))
      (ghczmprim:GHCziTypes.ZC @ ghczmprim:GHCziTypes.Int
       (ghczmprim:GHCziTypes.Izh (1::ghczmprim:GHCziPrim.Intzh))
       (ghczmprim:GHCziTypes.ZMZN @ ghczmprim:GHCziTypes.Int)))
     main:Main.cycliczqzq};

  %rec
  {main:Main.cycliczq :: ghczmprim:GHCziTypes.ZMZN
                         ghczmprim:GHCziTypes.Int =
     base:GHCziBase.zpzp @ ghczmprim:GHCziTypes.Int
     (ghczmprim:GHCziTypes.ZC @ ghczmprim:GHCziTypes.Int
      (ghczmprim:GHCziTypes.Izh (0::ghczmprim:GHCziPrim.Intzh))
      (ghczmprim:GHCziTypes.ZC @ ghczmprim:GHCziTypes.Int
       (ghczmprim:GHCziTypes.Izh (1::ghczmprim:GHCziPrim.Intzh))
       (ghczmprim:GHCziTypes.ZMZN @ ghczmprim:GHCziTypes.Int)))
     main:Main.cycliczq};
  arot :: ghczmprim:GHCziTypes.Int =
    ghczmprim:GHCziTypes.Izh (0::ghczmprim:GHCziPrim.Intzh);
  a1rou :: ghczmprim:GHCziTypes.Int =
    ghczmprim:GHCziTypes.Izh (1::ghczmprim:GHCziPrim.Intzh);

  %rec
  {main:Main.cyclic :: ghczmprim:GHCziTypes.ZMZN
                       ghczmprim:GHCziTypes.Int =
     ghczmprim:GHCziTypes.ZC @ ghczmprim:GHCziTypes.Int arot yrov;
   yrov :: ghczmprim:GHCziTypes.ZMZN ghczmprim:GHCziTypes.Int =
     ghczmprim:GHCziTypes.ZC @ ghczmprim:GHCziTypes.Int a1rou
     main:Main.cyclic};

如果我们稍微“清理”一下并删除一些ghczmprims 和诸如此类的东西，我们会得到

{cycliczqzq :: ZMZN Int = zpzp @ Int (ZC @ Int (Izh (0 :: Intzh)) (ZC @ Int (Izh (1 :: Intzh)) (ZMZN @ Int))) cycliczqzq};

{cycliczq :: ZMZN Int = zpzp @ Int (ZC @ Int (Izh (0 :: Intzh)) (ZC @ Int (Izh (1 :: Intzh)) (ZMZN @ Int))) cycliczq};

arot :: Int = Izh (0 :: Intzh);
a1rou :: Int = Izh (1 :: Intzh);

{cyclic :: ZMZN Int = ZC @ Int arot yrov;
 yrov :: ZMZN Int = ZC @ Int a1rou cyclic};

我们可以很容易地分辨出这一点cycliczqzq并cycliczq具有完全相同的定义，并且我们可以分辨出它们分别与cyclic''和相关cyclic'。对于cyclic，我们可以看出它是以不同的方式定义的。

编辑：

添加第四个定义

cyclic4 :: [Int]
cyclic4 =
    let xx = [1, 0] ++ yy
        yy = xx
    in xx

而且我还将它们全部重命名为cyclic1通过cyclic4以获得更好的可读性。-fext-core删除所有垃圾的输出是

{cyclic4 :: ZMZN Int = zpzp @ Int (ZC @ Int (Izh (1::Intzh)) (ZC @ Int (Izh (0::Intzh)) (ZMZN @ Int))) cyclic4};
{cyclic3 :: ZMZN Int = zpzp @ Int (ZC @ Int (Izh (0::Intzh)) (ZC @ Int (Izh (1::Intzh)) (ZMZN @ Int))) cyclic3};
{cyclic2 :: ZMZN Int = zpzp @ Int (ZC @ Int (Izh (0::Intzh)) (ZC @ Int (Izh (1::Intzh)) (ZMZN @ Int))) cyclic2};

aroR :: Int = Izh (0::Intzh);
a1roS :: Int = Izh (1::Intzh);
{cyclic1 :: ZMZN Int = ZC @ Int aroR yroT;
 yroT :: ZMZN Int = ZC @ Int a1roS cyclic1};

所以我们可以看到最后三个定义实际上变成了相同的字节码。

此外，这一切都是在没有优化的情况下编译的，因为这使得它更难阅读。

score 1 · Accepted Answer

扩展@PetrPudlak 示例提供了进一步的见解：

fix f = let x = f x in x

fix' f = f (fix' f)

k :: (Int -> Int) -> Int -> Int
k f 0 = 1
k f i = f $ i-1

main = do
         print $ fix k 10
         print $ fix' k 10

编译：

ghc -ddump-simpl -dsuppress-all c.hs

==================== Tidy Core ====================
Result size = 59

k_ra0
k_ra0 =
  \ f_aa4 ds_dru ->
    case ds_dru of wild_X6 { I# ds1_drv ->
    case ds1_drv of _ {
      __DEFAULT -> $ f_aa4 (- $fNumInt wild_X6 (I# 1));
      0 -> I# 1
    }
    }

main
main =
  >>
    $fMonadIO
    ($ (print $fShowInt)
       (letrec {
          x_ah6
          x_ah6 = k_ra0 x_ah6; } in
        x_ah6 (I# 10)))
    ($ (print $fShowInt)
       (letrec {
          fix'_ah0
          fix'_ah0 = \ f_aa3 -> f_aa3 (fix'_ah0 f_aa3); } in
        fix'_ah0 k_ra0 (I# 10)))

main
main = runMainIO main

很明显，第一种情况 ,fix构造一个常量一次，它在递归中被重用，但第二种情况 ,fix'必须在递归的每一步构造一个新的存根。

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

3 回答 3

Related

Reference