Having just begun my descent down the rabbit hole, I thought I’d try journaling about what I discover along the way, so that those who are merely curious can play the part of language voyeur. I’ve always wanted to do that: to see how someone dives into Erlang or O’Caml or Forth — or Haskell. Here’s your chance.

This is day 5 of the Haskell experience, and I’m having quite a bit of fun so far. It’s definitely twisting my head into pretzel shapes. I’ve spent hours getting less done than I could achieve with Python in moments. The hope is that all this retraining will pay off further down the road.

## Fibonacci

My first attempt was a Fibonacci function, which I failed at miserably. Turns out I was unable to conceive of “lazy recursion”. When I looked up the answer, it just seemed beautiful:

fib = 1 : 1 : zipWith (+) fib (tail fib)


This function starts out the list with 1, followed by 1, then it starts adding two lists together — provided by the same function before it’s even done! In imperative land this would blow the stack in a heartbeat, but in Haskell it makes sense. The recursive call to fib returns 1, 1, 2, 3, 5 and the recursive call to last fib returns 1, 2, 3, 5. Add them together, and you get the sequence.

There is also the traditional definition, which matches what you find in math textbooks:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)


If evaluated at the interactive prompt, this function will generate numbers forever, so you have to ask for just a few, like the first 20:

take 20 fib


So, things began with my face on the ground, which was humbling, but also refreshing that such a simple problem could floor me so easily.

## Splitting strings

The next problem I tried to tackle was splitting a string into substrings at each colon. That is:

"Hello:World"
=> ["Hello", "World"]


Again, fail. How shocking it was to spend over an hour on this and ultimately have to resort to Google. The answer was pretty straightforward:

splitAtColons :: String -> [String]
splitAtColons = sac' []
where sac' acc []       = [acc]
sac' acc (':':xs) = acc : sac' [] xs
sac' acc (x:xs)   = sac' (acc ++ [x]) xs


What I missed was using an accumulator to collect the current string. I kept thinking it was something I had to return as I went along, not passed down to each deeper level — and then returned after I’d added to it. Here’s the breakdown:

splitAtColons :: String -> [String]


Defines the type of the function as something which takes a String and returns a list of String.

splitAtColons = sac' []


This is essentially what I missed. The definition of splitAtColons calls a sub-function, passing in an empty string (aka list) as the “accumulator”.

    where sac' acc [] = [acc]


If sac' sees an empty string ([]) — the end of the string currently being processed — return the accumulated string in its own list.

          sac' acc (':':xs) = acc : sac' [] xs
sac' acc (x:xs)   = sac' (acc ++ [x]) xs


Otherwise, take apart the current string into its first character, x, and the remainder, xs. If that first character is a colon, return a list with the current accumulator as the head, and recurse to process the rest of the string (and so on). Otherwise, add the non-colon character to the current accumulator, and recurse to process the rest of the string.

## First reactions

Moral of my first story: prepare to be humbled. Google and IRC were a lifeline, and the people on #haskell, both helpful and patient. More soon.

### 10 Responses to “Journey into Haskell, Part 1”

1. As a point of comparison in Clojure (taken from Stuart Halloway’s book):

(defn lazy-seq-fibo
([]
(concat [0 1] (lazy-seq-fibo 0 1)))
([a b]
(let [n (+ a b)]
(lazy-seq
(cons n (lazy-seq-fibo b n))))))

(take 20 (lazy-seq-fibo))

Rich Hickey seems to have been very inspired by Haskell: immutable data structures, STM, and liberal use of lazy sequences.

2. Since your function appends to ends of lists, it will run in quadratic worst-case time, since append takes time linear in the length of the first list. More traditional for performance-conscious FP would be to prepend to a list and reverse the accumulator at the end.

It *is* possible to write this function without using an accumulator. You would just need to do some pattern-matching on recursive results.

3. Very good point, Adam. I’ll bear this in mind in future.

4. I think you may have mixed up ‘last’ with ‘tail’ – last takes the last element of the list, where tail takes the list with the first element dropped.

5. I think you mixed up ‘last’ and ‘tail’ in you definition of fibs.

Other than that, welcome down the Haskell Rabbithole.

6. Very enjoyable post! Just noted a tiny error in the definition for fib: s/last/tail/

7. Discover the haskell way of thinking problems was to me a kind of enlightenment, i hope it will be the same for you.
I learned a lot trying to solve (and solving) euler projects problems. It’s a good way to learn the tricks of a language. And I was pretty stunned when i saw how short and elegant were the solutions in haskell.

8. Well, the article is really the sweetest on this laudable topic. I concur with your conclusions and will eagerly look forward to your next updates. Just saying thanks will not just be enough, for the fantasti c lucidity in your writing. I will directly grab your rss feed to stay abreast of any updates. Admirable work and much success in your business endeavors!

9. My solution:

splitAtColons :: String -> [String]
splitAtColons “” = [""]
splitAtColons (‘:’:xs) = “”:(splitAtColons xs)
splitAtColons (x:xs) = let rest = splitAtColons xs
cabal install MissingH