[Haskell-cafe] Problem with continuations and typing

[Jerzy Karczmarczuk]

I resend a posting which has been blocked by some daemon according to whom
I am not a memeber of this list (and which has not been cleared by Simon M.)
==


I tried to cook-up a simple version of nondeterministic computations using the
two-continuation model. I got stuck on an 'infinite type' error, and my question
is: have you seen a *concrete* (really concrete) Haskell implementation of a
similar model, I could inspire myself on? (I know a few theoretical works on
that).
(And for pedagogical reasons I wanted to work this until the end without ever
using the magic word "monad"... No >>= nor other similar abominations.)

A generator is something which takes two continuations
* Failure continuation, a parameter-less function, for example

failure () = error "No more solutions"

* Success continuation, a function which takes two parameters
    *  a value which it may return
    *  another generator which may return further values. (This is a particular
       version of the model. There are others).

A trivial success continuation returns the intercepted value.

accept x gen = x      -- (or:  accept = const)

The trivial generators are the one which fails, and one which returns just one
fixed value:

nogen fcnt scnt = fcnt ()
unit x fcnt scnt = scnt x nogen

Getting the next generator (skipping the first value) may be obtained with

next gen fc sc = gen fc (\_ nxt -> nxt fc sc)

Of course   next (unit x) =-=> nogen.

Alternative. Here I got stuck.
Now, try to define the  (disj gen1 gen2). This is a generator which launches gen1
and if it fails, it launches gen2. But if gen1 succeeds, the 'next' generator it
provides should also invoke gen2 in the case of failure, and this is recursive.
So:

disj gen1 gen2 fc sc =
   gen1 (\_ -> gen2 fc sc) (\x nxt -> sc x (disj nxt gen2))

Intuitively it is OK, (e.g. works in Scheme). But Haskell protests,
(disj nxt gen2) cannot be typed. I do not ask why, I see myself...

An attempt to collect all the generated instances in a list fails as well
for the same reason:

glist gen =
   gen (\_->[]) (\x nxt -> x : glist nxt)

Even simpler, a generator which never fails, and returns zeros

zeros fc sc = sc 0 zeros

fails to compile as well. *I do not ask why, I know*.

But I would like to continue this exercice along these lines, without too much
exotism (no monads, yet...), for my students. Do you have any simple work-around?
Introduce some algebraic constructors? Perhaps higher-rank polymorphism could do
something (but then I would have to explain it to my folk...)
I would hate this...

Gracias.

Jerzy Karczmarczuk