Writing a counter function

Frank Atanassow franka@cs.uu.nl
Mon, 1 Jul 2002 09:32:02 +0200

Shlomi Fish wrote (on 29-06-02 17:30 +0300):
> I'm trying to write a counter function that would return a tuple whose
> first element is the current value and whose second element is a new
> counter.

John Hughes showed how to do this. Here is a closely related, more abstract
solution which employs existential types. First let me give a paradigmatic
example which is slightly different from what you want: streams.

  data Stream a = forall x. Stm x (x -> a) (x -> x)

Note that we hide the state type x. This lets us keep the implementation
hidden from the client.

  value (Stm state val next) = val state
  next (Stm state val next) = Stm (next state) val next
  both s = (value s, next s)
  unfold :: x -> (x -> a) -> (x -> x) -> Stream a
  unfold state val next = Stm state val next
  -- the naturals
  nats1 = unfold 0 id succ
  -- value nats1 = 0
  -- value (next nats1) = 1
  -- value (next (next nats1)) = 2 ...

In the example above, we use an integer for the state, project it out when we
need a value, and increment it to get the next state. Here's another way to do
it, using a state which is not an integer.

  nats2 = unfold [0..] head tail

Here we just used an infinite list for the state. head :: List Int -> Int, so
the state type is now different from "method" result type.

And here's an example where we use a step of 100 when we create the stream.

  -- step 100
  stm1 = unfold 5 id (+ 100)

But you wanted an object where we can choose the step at each "point in
time". OK:

  data MyStream a = forall x. MyStm x (x -> a) (a -> x -> x)
  myValue (MyStm state val next) = val state
  myNext arg (MyStm state val next) = MyStm (next arg state) val next
  myBoth arg s = (myValue s, myNext arg s)
  myUnfold :: x -> (x -> a) -> (a -> x -> x) -> MyStream a
  myUnfold state val next = MyStm state val next
  counter n = myUnfold n id (+)

Now the state-transforming function accepts an extra argument along with the
state. And in fact we were able to generalize the idea of "stepping", since we
never had to mention integers or addition till the last line.

Easy, right? You can see the pattern for defining similar sorts datatypes
now. Hide the state type x with a forall, and, for each way of observing and/or
transforming the state, include a function of type x -> ...

OO people call this a (functional) object. Mathematicians call it a
coalgebra. There is a notion of coalgebraic (or coinductive) datatype which is
dual to the notion of algebraic datatypes in Haskell; sometimes they're called
codatatypes. The analog of unfold is fold, of methods (sometimes called
destructors or observors) are data constructors, and of the state type is the
"accumulator" type which is the result of a fold. Some languages like Charity
support codatatypes directly, but in Haskell we can get the same effect with a
local forall.

Actually, you can make this even more OO-like using type classes, but things
seem to get messy if we keep the result type polymorphic so I'll fix it to

  class CounterState x where
    sValue :: x -> Integer
    sNext :: Integer -> x -> x
  data Counter = forall x. CounterState x => Counter x
  instance CounterState Integer where
    sValue = id
    sNext step state = step + state
  mkCounter :: Integer -> Counter
  mkCounter n = Counter n

A disadvantage of this approach is that now you can only have one
implementation for each state type; with unfold, where we stored the functions
in the data constructor fields, we could give many implementations of the
methods for each state type. In OO terms, the type class approach is
"class-based" whereas the unfold approach is "object-based".

The advantage, of course, is that you can use inheritance via the type class
inheritance now.

BTW, I hope that this note will not encourage the OO readers on this list to
"objectify" _everything_ now, because that leads (IMO) to twisted programs
which often emphasize the wrong sort of flexibility.

Both datatypes and codatatypes have their place:

  * A datatype is called for when you need a collection of finite-sized values
    (lists, trees, etc.), and want to be able to traverse them easily. The
    fold for a datatype does this for you, and is guaranteed to terminate.

  * A codatatype is called for when you have a collection of infinite-sized or
    circular values (streams, automata, etc.) and you want to be able to index
    arbitrarily into (grab subparts of) them, without possibility of error or
    exposing the representation.

Note that you cannot generally traverse a value of a codatatype: if you try
to "fold" a stream, the computation will diverge.

On the other hand, you cannot index arbitrarily deeply into a value of a
datatype. Remember our stream example? We could have called the "value"
function "head" and the "next" function "tail". You can always apply these to
a stream, and they will never fail. But if you try that with lists, you will
raise an error once you get to the end of it.

Frank Atanassow, Information & Computing Sciences, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-3261 Fax +31 (030) 251-379