CODEWITHSUNDEEP
haskellstream
Roxana Ciobanu
Roxana Ciobanu

Reputation: 273

Haskell understanding some functions

Can someone please explain why the first function generates the stream "a", "aa", "aaa" .. ? Or why the second generates a stream of prefixes for example: prefixes [1,2,3..] -> [[],[1],[1,2], [1,2,3]..]

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

Upvotes: 1

Views: 135

Answers (2)

bheklilr
bheklilr

Reputation: 54058

They're both pretty similar, so I'll just show you strings and let you figure out prefixes on your own as an exercise.

Haskell likes being both recursive and lazy. Laziness means that values are represented by thunks, or promises of future computations. You can actually see them in GHCi when you evaluate something:

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

Each _tN represents a pointer to the rest of the stream that hasn't been evaluated yet. You can also visualize it like this, where the _ represents the pointer to the rest of 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" : _)
                                         ^---------<----------^
    = ...

Hopefully this makes sense, each ^-<-^ shows what the _ is pointing at in each iteration (roughly)

Upvotes: 5

J. Abrahamson
J. Abrahamson

Reputation: 74354

These are both some really interesting "tying the knot" examples. You can understand them operationally by carefully following the evaluation, being sure to not evaluate too much ever. You can also understand them equationally. Sometimes the latter is easier

For instance, if we consider a slight variation on strings

strungs = map ('a':) strungs

we can think of the answer as being whatever value strungs goes unchanged if you map ('a':) over it. If we imagine strungs is a list of strings (and it must be by the types) then performing map ('a':) to that list adds a new 'a' to the front of each element.

Thus the only choice of strungs that goes unchanged after such a map is if it's a list of any length where each element is the infinite string "aaaaa...".

Now strings is a lot like strungs, but it has another condition. Whatever strings is, it has to be the same as "" : map ('a':) strings. It's easy to see that we're playing a similar kind of game here as we did with strungs, except that we keep adding new empty elements. Thus, strings must look like

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

because map ('a':) strings looks like

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

and then prepending "" makes it the same as what we started with

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

Upvotes: 7

Related Questions