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 Integer: 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