Haskell了解一些功能

Question

有人可以解释为什么第一个函数生成流"a"，"aa"，"aaa".？或者为什么第二个会生成前缀流，例如： prefixes [1,2,3..] -> [[],[1],[1,2], [1,2,3]..]

strings = "" : ( map ('a' :) strings )
prefixes (x : xs) = [] : ( map (x :) (prefixes xs) )

Answer 1

这些都是一些非常有趣的"打结"的例子。您可以通过仔细跟踪评估来在操作上理解它们，确保不要评估太多。您也可以等式地理解它们。有时后者更容易

例如，如果我们考虑strings的细微变化

strungs = map ('a':) strungs

我们可以把答案想象成任何价值strungs如果你map ('a':)它，它就会保持不变。如果我们想象strungs是一个字符串列表(它必须是按类型(，那么对该列表执行map ('a':)将在每个元素的前面添加一个新的"a"。

因此，在这样的映射之后保持不变strungs的唯一选择是，如果它是一个任意长度的列表，其中每个元素都是无限字符串"aaaaa..."。

现在strings很像strungs，但它有另一个条件。无论strings是什么，它都必须与"" : map ('a':) strings相同。很容易看出，我们在这里玩的是一种类似于strungs的游戏，只是我们不断添加新的空元素。因此，strings必须看起来像

"", "a", "aa", "aaa", "aaaa", ...

因为map ('a':) strings看起来像

"a", "aa", "aaa", "aaaa", "aaaaa", ...

然后前缀""使其与我们开始时相同

"", "a", "aa", "aaa", "aaaa", "aaaaa", ...

Answer 2

它们都非常相似，所以我只给你看strings，让你自己弄清楚prefixes作为练习。

Haskell喜欢递归和懒惰。 懒惰意味着价值由笨蛋或未来计算的承诺表示。 当你评估某些东西时，你实际上可以在GHCi中看到它们：

> let strings = "" : map ('a' :) strings
> :print strings
strings = (_t1 :: [[Char]])
> strings !! 0
""
> :print strings
strings = "" : (_t2 :: [[Char]])
> strings !! 1
"a"
> :print strings
strings = "" : "a" :: (_t3 :: [[Char]])
> strings !! 2
"aa"
:print strings
strings = "" : "a" : "aa" : (_t4 :: [[Char]])

每个_tN表示指向尚未评估的流其余部分的指针。 你也可以像这样可视化它，其中_表示指向其余部分的指针strings

strings
    = "" : map ('a':) strings
      ^--------<------^
    = "" : map ('a':) ("" : _)
           ^--------<-------^
    = "" : ('a':"") : map ('a':) (_)
           ^--------<-------------^
    = "" : "a" : map ('a':) ("a" : _)
                 ^-------<---------^
    = "" : "a" : ('a':"a") : map ('a':) (_)
                 ^---------<-------------^
    = "" : "a" : "aa" : map ('a':) ("aa" : _)
                        ^--------<---------^
    = "" : "a" : "aa" : ('a':"aa") : map ('a':) (_)
                        ^----------<-------------^
    = "" : "a" : "aa" : "aaa" : map ('a':) ("aaa" : _)
                                ^---------<---------^
    = "" : "a" : "aa" : "aaa" : ('a':"aaa") : map ('a':) (_)
                                ^------------<------------^
    = "" : "a" : "aa" : "aaa" : "aaaa" : map ('a':) ("aaaa" : _)
                                         ^---------<----------^
    = ...

希望这是有意义的，每个^-<-^都显示了_在每次迭代中指向的内容(大致(