Hacker Newsnew | comments | show | ask | jobs | submit login

Interesting that you can achieve such a close correspondence.

I know Lisp loves lists, but it's a bit strange to insist on them in Haskell when you could have replaced [ and ] with ( and ) and achieved a whole lot of type safety whilst preserving the semantics.

I wasn't insisting on lists, but on square brackets, to match McCarthy's syntax. This golf game has strict rules!

If we drop the brackets we may as well go the whole way and use curried functions, in which case the diff function looks like:

  diff y x =
    atom y → (eq y x → ONE $ ZERO) $

    eq (car y) PLUS → 
      cons PLUS (maplist (cdr y) (\z -> diff (car z) x)) $

    eq (car y) TIMES → 
      cons PLUS (maplist (cdr y) 
                  (\z -> cons TIMES 
                           (maplist (cdr y) 
                             (\w -> z /= w → car w $ 
                                             diff (car w) x)))) $
  error ("Unexpected term" ++ show y)


What do you mean? Nothing in that post is related to Lisp parenthesis syntax. It is a post about expressing a custom mathematical syntax in valid Haskell.

(Which is obviously a clever game and not a meaningful endorsement of the syntax, since statement syntax is not the point of McCarthy's paper.)


I mean that the Haskell version is not anywhere close to being type safe. If you change almost all of the [] to () you can achieve a great deal of type safety at no extra cost. Having said that, there's still a lot of low-hanging type safety fruit remaining! (I also took the liberty of removing Lambda, which was redundant).

    diff (y, x) =
      atom (y) → (eq (y, x) → ONE $ ZERO) $
      eq (car (y), PLUS) →
          cons (PLUS, maplist (cdr (y), \z -> diff (car (z), x))) $
      eq (car (y), TIMES) →
          cons (PLUS, maplist (cdr (y),
                               \z ->
                               cons (TIMES,
                                     maplist (cdr (y),
                                              \w ->
                                              z /= w → car (w) $
                                              diff (car (w), x))))) $
      error ("Unexpected term" ++ show y)
    mctest1 = diff (List [TIMES, X, List [PLUS, X, A], Y], X)
    data SExpr = ZERO | ONE | PLUS | TIMES | X | A | Y
               | List [SExpr]
               deriving (Eq, Show)
    car (List t) = head t
    car _ = error "car of non-pair"
    cdr (List t) = List (tail t)
    cdr _ = error "cdr of non-pair"
    cons (h, List t) = List (h : t)
    cons _ = error "cons with non-list" -- our lists aren't pairs

    atom (List _) = False
    atom _ = True
    eq (x, y) = x == y
    maplist (List x, f) = List (ml x)
       where ml [] = []
             ml x@(_:t) = f (List x) : ml t
    infixl 1 →
    (→) :: Bool -> a -> a -> a
    (→) True  x _ = x
    (→) False _ y = y


Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact