Take the 2-minute tour ×

I am a Haskell newbie, though had a previous Lisp/Scheme experience. Right now I am looking at the examples from SICP and trying to implement them in Haskell to get more hands-on experience. In the lecture 3b authors present a function for computing the derivatives symbolically. It contains, among others, the following lines:

(define (deriv exp var)
    (cond ((constant? exp var) 0)
          ((same-var? exp var) 1)
; ...

Further in the lecture, some more functions are defined:

(define (constant? exp var)
    (and (atom? exp)
         (not (eq? exp var))))

Is there a way to do same thing in Haskell, i.e. check for atomicity and symbolic equivalence to some other function? Or more general, what are the means of "disassembling" functions in Haskell?

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

Your Scheme examples don't actually examine Scheme functions. I recently did some symbolic differentiation in Haskell over values of the following type:

data Exp a = Lit a
           | Exp a :*: Exp a
           | Exp a :+: Exp a
           | Var String
  deriving Eq

Instead of discriminating using atom? or eq? you use case (or other pattern matching) and ==.

share|improve this answer
What about evaluating your Exp data (as far as I understand, this is ultimately a list)? –  Sergey Mikhanov Feb 14 '09 at 18:06
I actually didn't need an eval function; I was using symbolic differentiation to emit C code. If you want to write one and have trouble, post a question :-) –  Norman Ramsey Feb 14 '09 at 23:36
add comment

Firstly, although SICP is great, I would recommend against it for learning Haskell.(#) Some of the difficulty in this question stems from this.

In Lisp/Scheme, a 'function' is thought of a piece of code, and examining a function simply means examining its code. In Haskell, a 'function' means something closer to its mathematical definition, as a map from a set A to a set B. So for example, it make sense, in the Lisp context, to compare two functions: just compare their code. (But are (x+y)^2 and x^2+2*x*y+y^2 different functions?) In Haskell, it depends on whether there exists a constructive procedure for determining equality for the class of functions you are considering.

Similarly, as in your question, in Lisp/Scheme, you would write a "derive" function that differentiates correctly when given expressions, and just errors out or returns garbage on arbitrary inputs. Under Haskell's type system, this is (AFAIK) impossible to do, because—if you think about it—there is no such thing as differentiating an arbitrary input: you can only differentiate an Expression (or possibly a more general class, but still not everything). So as in Norman Ramsey's answer, you first define an "Expression" type (or type class), which is very simple to do, and then write the function

derive :: Expression -> Expression

that disassembles an Expression using the pattern-matching constructs (or something else depending on how Expressions were built up).

(#): The reason is that SICP has an entirely different philosophy, which involves using an untyped programming language and encouraging a lack of distinction between code and data. While there is some merit to the "code=data" argument (e.g. the fact that on the von Neumann architecture we use, "everything is 0s and 1s anyway"), it's not necessarily a good way of reasoning about or modelling problems. (See Philip Wadler's Why Calculating is Better than Scheming for more on this.) If you want to read a Haskell book with a functional flavour instead of a Real World one, perhaps Simon Thompson's Haskell: The Craft of Functional Programming or Richard Bird's Introduction to Functional Programming using Haskell are better choices.

share|improve this answer
add comment

I don't think you can do that. Lisp is homoiconic, Haskell isn't.

However, further Googling turned up Liskell, which is (?) an interesting hybrid.

share|improve this answer
Yeah, I though about homoiconicity. However, I don't need the functions, the data, and the program itself to be represented in the same way. The fact that algebraic data types' representation is different from the one of the program does not limit me in deconstructing them. –  Sergey Mikhanov Feb 13 '09 at 22:37
add comment

Your Answer


