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喜欢既递归又懒惰.懒惰意味着价值由thunks或未来计算的承诺表示.在评估某些内容时,您可以在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" : _)
                                         ^---------<----------^
    = ...

希望这是有道理的,每个都^-<-^显示_每次迭代中指向的内容(粗略)