Haskell Fold in Lisp

2008-09-05 13:48:23

I have been working my way through the beta version of the new O'Reilly Haskell book. So far it is a good read. The authors often try to make the concept clearer by making comparisons to other language. I found this helpful and annoying. The reason that I say it is annoying is it made me start to look for language comparisons that could be pointed out. For instance when talking about head, tail and list they never once mention lisp or at least scheme. At this point I also think that box and pointer diagrams may have been helpful. Another point where I felt a comparison might be helpful was when discussing pattern matching, prolog and erlang would have been good languages to mention. I know that these languages are not mainstream but if esoteric things like unions inside of structs in c are going to be used, to clarify a concept, then some less common language references might not be that much to ask for.

One new concept that I have learn from the book is the idea of folds. They use folds in the functional program chapter to explain common patterns in recursion. Map and filter are then implemented using right folds. Since I have never come across folds in lisp I translate the Haskell code to see how they might be implemented:

;; Haskell reminds me of perl in the fact that it has a rich syntax and
;; ways to structure your statements so that your programs are easier to
;; read. The problem with rich syntax is that you have to remember all of
;; it.

(defun create-list (start stop &key (step 1))
  "Works like Haskell enumeration notation [1..n] syntax. A step value can be passed to
control the difference between two numbers."
  (cond
    ((> start stop) '())
    (t (cons start
             (create-list (+ start step) stop :step step)))))

;; foldl _ zero []        = zero
;; foldl step zero (x:xs) = foldl step (step zero x) xs

(defun foldl (step zero lat)
  "Fold to the left."
  (cond
    ((null lat) zero)
    (t
     (foldl step
            (funcall step zero (first lat))
            (rest lat)))))

;; foldr _    zero []     = zero
;; foldr step zero (x:xs) = step x (foldr step zero xs)

(defun foldr (step zero lat)
  "Fold to the right."
  (cond
    ((null lat) zero)
    (t
     (funcall step
              (first lat)
              (foldr step zero (rest lat))))))

;; myFilter p xs = foldr step [] xs
;;    where step x ys | p x       = x : ys
;;                    | otherwise = ys

(defun filter (func lat)
  "Filter returns a list of all of the items, from the passed list,
that func returns true on."
  (flet ((my-step (x ys)
             (cond ((funcall func x) (cons x ys))
                   (t ys))))
    (foldr #'my-step '() lat)))

(defun odd (n)
  (= 1 (mod n 2)))

(defun even (n)
  (= 0 (mod n 2)))

(defun my-map (func lat)
  "Implementation of map using right fold."
  (flet ((my-step (x ys)
             (cons (funcall func x) ys)))
    (foldr #'my-step '() lat)))

(defun square (n)
  (* n n))

If you want a list of all odd number between 1 and 100 you could say:

CL-USER> (filter #'odd (create-list 1 100))

My version of create-list sucks in comparison with Haskell's enumeration notation. In Haskell the item from the list is not created until you actually need it allowing for you to have infinite list. One more thing, I haven't even finished the book so I'm sure my observations are weak and premature.