Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Examining the internals of the functions in Haskell

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?

like image 974
Sergey Mikhanov Avatar asked Feb 13 '09 22:02

Sergey Mikhanov


2 Answers

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.

like image 75
ShreevatsaR Avatar answered Oct 20 '22 16:10

ShreevatsaR


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 ==.

like image 20
Norman Ramsey Avatar answered Oct 20 '22 16:10

Norman Ramsey