Pointers in Haskell??

Jan Kort kort@science.uva.nl
Fri, 07 Dec 2001 18:16:49 +0100


"Bryan Hayes (Hayes Technologies)" wrote:
> 
> I am totally new to Haskell, so maybe this is a stupid question.
> Various languages have pointers (or references), for good reason.
> Haskell can at least partly do without them (they are only existing internally somehow).
> My question is: Does Haskell principally not need pointers (i.e. in case of 2 data structures needing to reference an other very
> large data structure) or is this a design flaw or have a overlooked something?

All Haskell compilers use pointers internally. The
idea is that because Haskell is referentially
transparent and side effect free, you can overwrite
a function application with its result. For example,

let
  x = [1..1000]
in
  foo (A x) (B x)

Will internally have "x" pointing to the function
application [1..1000], when this function application
is evaluated it will overwrite the memory cell "x"
points to with the result. So eventually it will
look like this:

 +---+---+   +---+---+
 | A | x |   | B | x |
 +---+---+   +---+---+
       |           |
       +---+-------+
           |
           V
       +---+---+------+
       | : | 1 | tail |---> The list 2..1000
       +---+---+------+

Where each block is a memory cell and each arrow is a
pointer. A book that describes this a lot better is:

    Simon Peyton-Jones. The implementation of functional
    programming languages. Prentice-Hall, 1987

  Jan