Could someone explain these Haskell functions to me?

Question

I've dabbled with Haskell in the past, and recently got back into it seriously, and I'm reading real world haskell. Some of the examples they've shone, I've yet to understand. Such at this one:

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

I don't see how this works, what is 1 really being added too? How is the recursion returning something that can be added to? I don't get it.

And here we have this one:

splitLines [] = []
splitLines cs =
       let (pre, suf) = break isLineTerminator cs
       in  pre : case suf of 
                   ('\r':'\n':rest) -> splitLines rest
                   ('\r':rest)      -> splitLines rest
                   ('\n':rest)      -> splitLines rest
                   _                -> []

isLineTerminator c = c == '\r' || c == '\n'

How does this work, what is pre really being attached too? I don't see how the the result of the case expression is something that pre can be concatenated to. Maybe I just need someone to explain the evaluation of these functions in details. I must be missing something very vital.

Thanks in advance!

EDIT: I know, it was a copy-paste fail. Sorry.

EDIT 2: It seems my confusion was with what these functions were actually /returning/ I have it all worked out now. Thanks for the answers guys, it finally clicked! I appreciate it!

Answer 1

I think the definition of myLength misses the case where the list is empty:

myLength [] = 0
myLength (x:xs) = 1 + myLength (xs)

With this definition, the myLength of an empty list is 0. The (x:xs) patten unpacks a list into the first item, a, and a list with the rest of the items, xs. If the list has one item, then xs is an empty list, so the result is 1 + 0. And so on.

Recursion is easiest to understand when you look at the base case first, and then see how each level of recursion builds on the result. (The base case is the case where the function does not call itself. If a recursive function doesn't have a base case, the output will be infinite.)

In the second example, the base case (the last case in the case-statment) is also an empty list. So pre will always be appended to a list, which will yield a new, longer, list.

Answer 2

Re: myLength (x:xs) = 1 + myLength (xs) -- this is "half" of the definition of myLength, it says, by pattern match, that if the argument has a head and a tail, then the result is one more than the recursive tail call on the tail -- there needs to be another half to say that the result is 0 when the argument cannot match x:xs, i.e., when the argument is an empty list.

In the second case, the possibility of different patterns matching is just made a bit more epxlicit via case.

BTW, laziness is not a key issue here -- ML, with eager evaluation but pattern matching much like Haskell, would work very similarly. Looks like pattern matching is what you really need to brush up about.

Answer 3

First of all the first example should be like this (edit: it looks like you fixed it now):

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

It works like this: say I give it a list with three items, it returns one plus the length of the tail (which is one plus the length of the tail (which is one plus the length of the tail, (which is [] at this point), which is 1), which is w), which is 3 (the final answer). Maybe nested parenthesis will help you understand it. ;-)

Answer 4

It is instructive to look at what the type signatures of the functions would be. They could be:

myLength :: [a] -> Int

In myLength, 1 is being added to the result of the recursive call to myLength, which is an Int, which in turn results in an Int.

splitLines :: [Char] -> [[Char]]

In splitLines, pre (a [Char]) is being prepended to the result of the case statement, which, from looking at the cases, is either the result of a recursive call to splitLines, which is [[Char]]; or an empty list. In both cases, prepending pre (a [Char]) will result in a [[Char]] in turn.

Answer 5

As for the first one, it's a very basic way of recursion. However, it seems to be missing a part:

myLength [] = 0

It works by scaling off one element at the time from the list and adding one to the result. To visualise, consider the call

myLength [1,2,3]

which will evaluate to:

1 + myLength [2,3]
1 + 1 + myLength [3]
1 + 1 + 1 + myLength []
1 + 1 + 1 + 0

which is 3.

As for the second one, well, you have already split the string at the next line break into two parts: pre and suf. Now, suf will start with either a \n, or a \r, or a \r\n. We want to remove these. So we use pattern matching. See how the rest variable is essentially the suf variable minus the initial line break character(s).

So we have pre, which is the first line, and rest, which is the rest of the text. So in order to continue splitting rest into lines we call splitLines on it recursively and concatenate the result to pre.

To visualize, say you have the string "foo\nbar\r\nbaz".

So, when calling, the result will be:

[ pre => foo, suf => \nbar\r\nbaz, rest => bar\r\n\baz ]
foo : splitLines bar\r\nbaz

then splitLines is called again, and the result is expanded into:

[ pre => bar, suf => \r\nbaz, rest = baz ]
foo : bar : splitLines baz

then once again:

[ pre => baz, suf => [], rest = [] ]
foo : bar : baz

which is the final result.