data Sexp = Int Int | Nil | Cons Sexp Sexp
megasum Nil = 0
megasum (Int i) = i
megasum (Cons l r) = megasum l + megasum rIndeed. The first step to grokking Lisp, from Haskell (or any typed language), is to realize that Lisp's "list" is not equivalent to any single data type you've used before, but it's really a general weakly-structured representation of any and all structured types.
Even this solution is not completely equivalent to Lisp megasum -- it fails to compile on the list `('a)` ;-)
Totally got sucked in, and an hour or so later I had finished. Accounting for all those parens was really frustrating at first, but with the help of a good editor I eventually feel like I got into the "Lisp headspace."
I have played around with Haskell a bit. Scheme feels more verbose, but also closer to the metal^H^H^H^H^Hlambda calculus. The feature I missed the most was currying:
You can get around this somewhat: The dynamic typing was also a bit foreign for me, so it took a while for me to wrap my head around "megasum." I can vaguely imagine how to implement it in Haskell, but it wouldn't be pretty!