21Dec

Thinking In Haskell is harder than Thinking In Portals

Posted by Elf Sternberg as programming

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.

2 Responses to Thinking In Haskell is harder than Thinking In Portals

Leo

July 21st, 2013 at 5:01 am

Prelude> let rev [] = []; rev (x:xs) = (rev xs) ++ [x] in rev “Hello, World”

“dlroW ,olleH”

I guess it’s much better than your but still I don’t think that’s an idiomatic way to reverse a list in Haskell

Leo

July 21st, 2013 at 5:10 am

Here we go, the idiomatic way to reverse a list:

Prelude> foldl (\xs x -> x:xs) [] “Hello, World”

“dlroW ,olleH”

Comment Form

Subscribe to Feed

Categories

Calendar

December 2011
M T W T F S S
« Nov   Jan »
 1234
567891011
12131415161718
19202122232425
262728293031