Sunday, June 17, 2018

Lazy evaluation and list random access in Haskell

Lazy evaluation and list random access in Haskell

Today I learned about the :sprint command in GHCi, which prints the value bound to given identifier without forcing its evaluation. The unevaluated part, if any, is printed as an underscore.

Here, we can see that the value bound to s is entirely unevaluated at first:

λ> s = "0123456789"
λ> :sprint s
s = _

Now let’s peek at the first character in the string:

λ> head s
'0'
λ> :sprint s
s = '0' : _

We can see that only the first character in the string (i.e. the first element of a list of characters) was evaluated. Now, let’s use the !! operator to print the fourth character in s:

λ> s !! 3
'3'
λ> :sprint s
s = '0' : '1' : '2' : '3' : _

Interesting – we can see that this caused all of the intervening elements to be consumed, which demonstrates that random access of a list with the !! operator must walk along the cons cells and therefore can be expected to require linear time to complete.

If we print the whole string, then :sprint shows the entire string with no unevaluated component:

λ> s
"0123456789"
λ> :sprint s
s = "0123456789"

No comments:

Post a comment