Am Dienstag, 8. März 2005 17:31 schrieben Sie: > Daniel Fischer wrote: > >The problem is that for the recursion combinators we need polymorphic > >recursion functions. > >For fact3 we need > >rec2 :: forall l. (HCons a (HCons a l) -> HCons a l), > > I dont see why this is illegal... what do we want? take the top two > items from the stack?
It's illegal, because a type variable may not be instantiated by a forall-type; section 7.4.9 of the user's guide: There is one place you cannot put a forall: you cannot instantiate a type variable with a forall-type. So you cannot make a forall-type the argument of a type constructor. So these types are illegal: x1 :: [forall a. a->a] x2 :: (forall a. a->a, Int) x3 :: Maybe (forall a. a->a). I'd say that also applys to HList, HCons (forall l. (HCons a (HCons a l) -> HCons a l)) blah won't work (and my ghci doesn't swallow it). > > Take the to N elements from the stack: > > class Take l n h t | l n -> h t where > take :: l -> n -> (h,t) > instance Take l HZero HNil l where > take l _ = (HNil,l) > instance Take t n (h',t') => Take (HCons h t) (HSucc n) (HCons h h',t') > where > take (HCons h t) (_::HSucc n) = (HCons h h',t') > where (h',t') = take t (undefined::n) > Good, but cumbersome. And I'm not sure what the type signature should be for genrec (HCons rec2 (HCons rec1 (HCons t (HCons b stack)))) | hHead (b stack) = t stack | otherwise = rec2 (HCons (genrec.quote rec2.quote rec1.quote t.quote b) (rec1 stack)) I dare say it would be easier in Haskell-style: genrec rec2 rec1 t b stack. > >For the general recursion combinator it's even worse, because > >rec2 may take n2 elements of certain types from the stack, does something > > with them and put k2 elements of certain types determined by the types of > > the consumed elements on the stack, leaving the remainder of the stack > > unchanged, rec1 takes n1 elements etc. And the numbers n2, n1 . . . and > > the types depend on the supplied recursion functions. > >So (reverting to nested pairs notation), we would have to make linrec to > >accept arguments for rec2 of the types > >(a,b) -> (r,b), > >(a,(a1,b)) -> (r,(r1,(r2,b))), > >(a,(a1,b)) -> (r,b) > >(a,(a1,(a2,b))) -> (r,b) > > > >and so on, for arbitrary munch- and return-numbers, where we don't care > > what b is. These can't be unified however, so I think it's impossible to > > transfer these combinators faithfully to a strongly typed language. > > [Dynamic] won't work either, I believe, because Dynamic objects must be > > monomorphic, as I've just read in the doc. > > > >The point is, in Joy all these functions would have type Stack -> Stack > > and we can't make a stack of four elements the same type as a stack of > > six elements using either nested pairs or HLists (correct me if I'm > > wrong, you know HList better than I do). > > They are not the same type, but that are the same Kind, or Type-Familly... Aye, but as I understand it, once we push the recursion functions on the stack, they must be monomorphic, which means, the scheme won't work in general. > > class Stack s > instance Stack HNil > instance Stack s => Stack (HCons a s) Isn't this exactly the HList class? > > isItAStack :: Stack s => s -> s > isItAStack = id > > >However, Joy has only very few datatypes (according to the introduction I > >looked at), so > > > >data Elem = Bool Bool > > > > | Char Char > > | Int Integer > > | Double Double > > | String String > > | Fun (Stack -> Stack) > > | List [Elem] > > | Set [Int] > > > >type Stack = [Elem] > > > >type Joy = State Stack (IO ()) > > > >looks implementable, probably a lot to write, but not too difficult - > > maybe, I'll try. > > The above can be translated to HLists, the difference is that with > HLists the types (classes) > are extensible. Might well be, only I don't see how (would have to take a lonnnnnnnng look at HList, probably). Of course, doing it the primitive way means a lot of work every time you add a new datatype :-( But for these types, I did it (with a few modifications) and all works fine. > > There appears to be no IO in the example Joy code so existentials are > unneccessary. No IO around, I only thought I might wish to write an interactive frontend, printing out the top of the stack (might be an error message) after each step. I haven't got round to that yet, and I don't know whether I will, but I think if I do, I'd better use type Joy = IO (State Stack Elem). > > Keean. Daniel _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe