Thinking in Haskell is harder than Thinking in Portals

[elfs]

I used to joke that, sometimes, when someone in my family comes down and sees a mess of code up in Emacs on my screen that "No, really, I'm playing a video game. It just looks like work." Because I find coding fun. But the fact is that I also play games, and Portal 2 was definitely a brain-bender.

But not as brain-bending as Haskell.

That said, I just finished the first exercise in Seven Languages in Seven Weeks, although really I'd think it's more like Seven Languages in Seven Days, given my ferocious language consumption-- I just skipped right to the Haskell part, because I have a project that requires Haskell at the moment. Still, this was pretty cool. Don't read further if you don't want the answer.

The problem was "Write a function that reverses a list." In most languages, that's pretty simple. In Haskell, not so much. This problem requires three leaps: First, to understand that "strings are lists of characters" means exactly what it says, so the thing introduced earlier as a "String concatenation infix operator" is in fact a list concatenation infix operator, and finally take the Fibonacci example, with its helper functions and patterns, and apply that idea to this problem.

    reverseSub :: ([x], [x]) -> ([x], [x])
    reverseSub (xs, []) = (xs, [])
    reverseSub (xs, (h:t)) = reverseSub([h] ++ xs, t)

    reverse1 :: [x] -> [x]  
    reverse1 [] = []
    reverse1 xs = (fst . reverseSub) ([], xs)

The function I'm defining I'm defining takes a list and returns a list. If the list is empty, return an empty list. Otherwise, return the first item in the tuple returned by reverseSub, to which I provide an empty list and my initial list.

reverseSub, in turn, takes a tuple of two lists, and returns a tuple of two lists. The first pattern says "If the second list is empty, return the tuple unchanged." The second pattern means "Otherwise, reverseSub of two lists is "the head of the second list concatenated with the first list, and the tail of the second list," applied recursively. It still feels totally weird to me that Haskell would automatically apply the second operation again and again until the first is met; I understand it intellectually, in a super-cool, I-love-recursion way, but it doesn't quite resonate yet.

Still, this is way fun.

Comments

[en-ki.livejournal.com]

Now write "du" without creating a memory leak.

I'll wait.

[atheorist.livejournal.com]

I am not much of a Haskell programmer, but I would bet that "concatenation infix operators" is not the way you want to be thinking about list reverse in Haskell. Infix is just sugar, and ++ is just another function that takes lists and returns lists. The syntax for constructing a list from a head and a tail is primitive, and identical to the syntax for pattern matching / destroying a list.

I think you meant to write something more like this:

reverse xs = reverseHelper [] xs
reverseHelper accum [] = accum
reverseHelper accum (head:tail)) = reverseHelper (head:accum) tail

[elfs.livejournal.com]

See, this is why I want to learn Haskell. I described what was clear in my head as a procedure for reversing a list; you described an even clearer reversal.

It's still the inherent and automatic recursion that bugs me most. I know I'll get used to it.

[atheorist.livejournal.com]

I think it's no more or less "inherent and automatic" than anything else.

In Python, your code would look something like:

def reverseSub(accum, xs):
    if xs:
        h, t = xs[0], xs[1:]
        return reverseSub([h]+accum, t)
    else:
        return accum, []

def reverse1(xs):
    if xs:
        return reverseSub([], xs)[0]
    else:
        return []

Is that 'inherent and automatic' recursion? It's just ordinary function calls.

[elfs.livejournal.com]

True enough. It's just odd that everything seems recursive in Haskell. I've become a fan of recursion through Javascript, oddly; I was never very happy with my comprehension of it when working in C, and Python has such sweet functional pieces that I didn't need to abstract my thinking that far.

*Sigh* I'm sure I'll get it. But it won't be an epiphany. It'll just one day be "that's the way I've always done it."

[blaisepascal]

A classic book you should consider picking up sometime is "The Little Lisper" (or it's more recent version, "The Little Schemer") http://www.ccs.neu.edu/home/matthias/BTLS/

It's Lisp/Scheme based, starts from very beginning basics (which might make an experienced developer think it's too basic), but really, really gets into recursion heavily. I think there's nary an iteration in the book, except those implemented recursively.