CODEWITHSUNDEEP
haskell
jtht
jtht

Reputation: 813

How are Haskell guards evaluated?

I'm doing the 99 Haskell Problems and in one of the solutions I came across the following code:

pack' [] = []
pack' [x] = [[x]]
pack' (x:xs)
    | x == head  h_p_xs = (x:h_p_xs):t_p_hs
    | otherwise         = [x]:p_xs
    where p_xs@(h_p_xs:t_p_hs) = pack' xs

I'm wondering when pack' gets called in the first guard and if this is a common pattern in Haskell code to reference the head and tail of the list returned from a function call. Are there multiple calls to pack' at any levels of recursion and is this a fast solution?

Upvotes: 4

Views: 813

Answers (3)

chi
chi

Reputation: 116174

I'm wondering when pack' gets called in the first guard

The guard x == head h_p_xs forces the evaluation of h_p_xs, which triggers the recursive call.

and if this is a common pattern in Haskell code to reference the head and tail of the list returned from a function call.

I think this is a quite common pattern. You might also find variations using case pack' xs of ... or let ... = pack' xs in ... instead.

Note that using let or where with a pattern such as h_p_xs:t_p_xs will cause a runtime error whenever an empty list is found. This code is careful to ensure the recursive call will not return an emlty list.

Are there multiple calls to pack' at any levels of recursion

To be pedantic, the Haskell standard does not specify how code is actually evaluated but only what is the result. So, in theory, the compiler is allowed to make any number of recursive calls.

Pragmatically, compilers will be careful to make just one recursive call -- not doing that would lead to a horrible performance.

For the sake of comparison, the code below is equivalent, but would lead to an exponential complexity (!)

...
where p_xs = h_p_xs:t_p_hs
      h_p_xs = head (pack' xs)
      t_p_xs = tail (pack' xs)

Here, you can expect the compiler to make two recursive calls.

and is this a fast solution?

Yes. It is expected to run in linear time on the input.

Upvotes: 2

Vinay Emani
Vinay Emani

Reputation: 340

pack' seems to work like Data.List.group - It groups successive equal elements into a list. So, pack' [1,1,3,2,2] shall return [[1,1], [3], [2,2]].

Pattern matching is idiomatic haskell. Here, in the statement,

h_p_xs:t_p_hs = pack' hs

we know pack' hs returns a list. So, h_p_xs is matched to its head while t_p_hs is matched to its tail. Both the LHS and RHS must have the same structure like here (both sides here have the list structure) for pattern matching to work in Haskell. p_xs gets matched to the whole RHS here(@ pattern). So, yes, this is a very common idiom in Haskell.

In pack' definition, the first two lines take care of the empty and singleton lists. So, the first guard condition is applicable only when the input list has more than one element and its first and second elements are equal.

At any level, there's at max one recursive call to pack', so time complexity is O(n) in length of the list. Should be fast.

Upvotes: 2

Eugene Sh.
Eugene Sh.

Reputation: 18371

This is a common way to reference head, if it makes the code more readable. Of course, you could do it by doing on the last line something like 

p_xs@(  (h_p_x : h_p_xs)  : t_p_hs) = pack' xs

instead of 

p_xs@( h_p_xs : t_p_hs ) = pack' xs

Such that you get the head in the h_p_x variable. But then you need to add in the fourth line: 

| x == head  h_p_xs = (x : h_p_x: h_p_xs):t_p_hs

So you see, that using the : operator here just cluttering the code by adding useless entities. As for number of recursions, I can see only one recursive call at each level here, so basically it is linear run time, and thus effective.

Upvotes: 1

Related Questions