How to stop infinite pattern-matching in Haskell?

Question

I am doing Exercise 3 from Homework 2 in http://www.cis.upenn.edu/~cis194/spring13/lectures.html

build :: [LogMessage] -> MessageTree
build [x] = Node Leaf x Leaf
build [x,y] = Node (build [x]) y Leaf
build [x,y,z] = Node (Node (build [x]) y Leaf) z Leaf

I have a problem where I do not know how to end the pattern matching. It would just keep expanding to [x,y,z,_] and then [x,y,z,_,_] and so on. How do I stop this?

This is a left fold - i.e. see [this graphic](http://image.slidesharecdn.com/fp-by-examples-130723041014-phpapp01/95/functional-programming-by-examples-using-haskell-28-638.jpg?cb=1374552694) — ErikR, Jun 26 '16 at 00:09
It's kind of funny that I ran into a related problem myself recently, trying to push my temporary allocation in a list-to-tree function onto GHC's evaluation stack. In the end, I concluded the only way was probably to have one line for each tree spine shape, which is *way* too many lines. — dfeuer, Jun 28 '16 at 16:01

score 4 · Accepted Answer · answered Jun 26 '16 at 00:27

When you are working with functions that take in lists, you will often want to work with recursion and list element functions.

Let's take a look at what you have so far.

On the fourth line, you have build evaluate to the following when it receives a list with three elements:

build [x,y,z] = Node (Node (build [x]) y Leaf) z Leaf

On the third line, you have build evaluates as follows when it receives a list of two elements:

build [x,y] = Node (build [x]) y Leaf

If you look at those two lines, you can notice that there is a bit of repetition. Specifically both contain Node (build [x]) y Leaf. When there is repetition like this, recursion can help.

Using recursion, you can replace that repetition with a recursive call of the build function with a list of two elements. For example, you could replace line four with:

build [x,y,z] = Node (build [x,y]) z Leaf

That makes it a little bit simpler, but it doesn't yet solve the problem.

build :: [LogMessage] -> MessageTree
build [x] = Node Leaf x Leaf
build [x,y] = Node (build [x]) y Leaf
build [x,y,z] = Node (build [x,y]) z Leaf

If you take a look at the new function, you can see that some of the constants that we are using could be replaced by using list element functions, like head, tail, last, and init.

In each pattern of the function we only treat the last element of the list separately. The non-last elements are then passed back into build. Thus we can get rid of some of the pattern matching by using last to access the last element of the list, and init to get all of the elements except for the last element.

build :: [LogMessage] -> MessageTree
build [x] = Node Leaf x Leaf
build l = Node (build (init l)) (last l) Leaf

By working with general list elements using init and last, instead of working with explicitly specified elements of a list, we can remove the need for infinite pattern matching.

In this case, since you were working with the list elements from last to first, the `(x:xs)` list pattern matching wasn't directly usable. But generally in the future you should try to get your functions work from the first element to the last, that way you can make use of the `(x:xs)` list pattern matching in order to make the function easier to write and understand. — Christopher Wells, Jun 26 '16 at 00:52
@Amorris repeatedly calling `init` is quadratic time behavior *(in strict languages...)*, and is what I tried to avoid. related: http://stackoverflow.com/questions/19944969/prolog-accumulators-are-they-really-a-different-concept/19951540#19951540, explaining a common programming technique that lets us make use of the `(x:xs)` pattern in such situations. — Will Ness, Jun 26 '16 at 05:53

score 2 · Answer 2 · answered Jun 26 '16 at 00:07

Rewrite your code in forward-calculating, accumulative style:

build [x] = go Leaf [x]
  where
  go tree (x:xs) = go (Node tree x Leaf) xs  -- build up ("accumulate") the tree 
  go tree []     = tree                      -- and reduce the list until empty

build [x,y] = go (Node Leaf x Leaf) [y]      -- can we use another, simpler 
  where                                      --   initial accumulator value?
  go tree (x:xs) = go (Node tree x Leaf) xs
  go tree []     = tree

....

Can you simplify this now? Do you notice the similarity here? Can build be called with a list of any length, i.e. matching the (x:xs) pattern?

score 1 · Answer 3 · answered Jun 26 '16 at 00:05

You might like the pattern x:xs, which matches any (non-empty) list, binding x to the first element and xs to the remaining elements. It is commonly used in conjunction with a recursive definition to inspect each element of a list in turn, no matter how long the list is.

If you want to match lists longer than, say, three elements, the pattern can be extended to x:y:z:rest; in this case, x, y, and z will be bound to the first three elements of the list, and rest will be bound to the remaining elements.

score 1 · Answer 4 · answered Jun 26 '16 at 00:06

You need to write this function recursively, by finding a way to make one complicated case solvable in terms of a simpler case. Because what you are pattern-matching is a list, you will use the (x:xs) pattern, to break a list down into its head and its tail. Something like this:

build :: [LogMessage] -> MessageTree
build [] = ... -- remember lists can be empty!
build [x] = Node Leaf x Leaf
build (x:xs) = -- something to do with build [x] and xs

How to stop infinite pattern-matching in Haskell?

4 Answers4