Re: Writing a counter function
John Hughes wrote: On Sun, 30 Jun 2002, Jon Cast wrote: Mark Carroll [EMAIL PROTECTED] wrote: On Sat, 29 Jun 2002, Samuel E. Moelius III wrote: (snip) Here's another not-exactly-what-you-wanted solution. :) (snip) Do any of the experimental extensions to Haskell allow a what-he-wanted solution? I couldn't arrange one in H98 without something having an infinitely-recursive type signature. That's because the problem requires an infinitely-recursive type. (snip) It isn't particularly hard to implement this. Haskell typecheckers use unification to match types up; the only difference is that a graph unification algorithm would be needed instead. Such algorithms exist --- the only real difference is you have to remember what you're unifying to avoid falling into a loop when unifying graphs with cycles. The idea of adding this to Haskell has been proposed several times, but never implemented. And the reason for THAT is that it would make type errors significantly harder to understand. (snip) Yes, but the dreaded Monomorphism Restriction was added for the same reason, wasn't it? Haskell allows us to get around the M.R. by using explicit type signatures where required. It seems to me that we could allow recursive types in the same way -- simply require a type signature for toplevel objects with recursive types. Is there a reason why this wouldn't work? Regards, Matt Harden ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
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
Re: Writing a counter function
Mark Carroll [EMAIL PROTECTED] wrote: On Sun, 30 Jun 2002, Jon Fairbairn wrote: (snip) But there's the rub. It's not beautiful and it doesn't make much sense. I really wish we could get away from the How do I convert this imperative code snippet into Haskell questions into How do I solve this abstract problem? The question as originally posed didn't seem like it particularly needed something imperative though. That largely misses the point. My objection is to the mindset behind the question. the first bit is very similar to, say, counter a = (a, \to_add - counter (a + to_add)) Which looks to me like imperative programming. Indeed, the Monad answer that I posted is imperative programming, it just happens to be done in Haskell. Stepwise transformation of a state is, on some occasions, the right answer to a problem. Unfortunately in this thread we haven't been told what the problem is. The question is of the form how do I make a hammer? when a hammer is rarely the most appropriate tool. That's what I'd like to get away from. Jón -- Jón Fairbairn [EMAIL PROTECTED] 31 Chalmers Road [EMAIL PROTECTED] Cambridge CB1 3SZ+44 1223 570179 (after 14:00 only, please!) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
On Sun, 30 Jun 2002, Jon Cast wrote: Mark Carroll [EMAIL PROTECTED] wrote: On Sat, 29 Jun 2002, Samuel E. Moelius III wrote: (snip) Here's another not-exactly-what-you-wanted solution. :) (snip) Do any of the experimental extensions to Haskell allow a what-he-wanted solution? I couldn't arrange one in H98 without something having an infinitely-recursive type signature. That's because the problem requires an infinitely-recursive type. Consider Haskell: self-apply f = f f The *typing algorithm* (the thing that didn't complain in Lisp) proceeds roughly as follows: f is applied to at least one argument, so f must have type a - b. Therefore, f's argument (f) must have type a. So, we conclude: f :: a - b f :: a But f can only have one type, so we set its types equal: a = a - b This is clearly recursive, right? so I'm wondering if it could be at all sane for Haskell to allow such stuff Sure. All it has to do is: 1. Create its own newtype in response to such things as `self-apply' above. 2. Ensure that self-apply f = f f and self-apply' g = g g have the same type. I would *love* to hear ideas on how to do that, but it's difficult. It isn't particularly hard to implement this. Haskell typecheckers use unification to match types up; the only difference is that a graph unification algorithm would be needed instead. Such algorithms exist --- the only real difference is you have to remember what you're unifying to avoid falling into a loop when unifying graphs with cycles. The idea of adding this to Haskell has been proposed several times, but never implemented. And the reason for THAT is that it would make type errors significantly harder to understand. Consider f x y = if x==0 then y else f (x-1) (where I forgot the second parameter in the recursive call). We expect this to be a type error, and indeed it is --- BECAUSE recursive types are not allowed. If they were, this definition would be well-typed, with the type f :: Num a = a - bwhere b = b - b You wouldn't get an error message unless you tried to CALL f, and perhaps not even then. For example, f 1 2 :: Num b = b where b = b - b is well-typed! So you would probably eventually, somewhere else in the program, see an error message of the form ERROR - Illegal Haskell 98 class constraint in inferred type *** Type : Num b = b where b = b - b This is enough to scare most people off the idea. Think of all the times you've seen the error message unification would give infinite type It's not the most common kind of type error, but it does happen regularly, at least to me. In every such case, the type error would be deferred in the way I describe. If I remember rightly, OCaml allows type recursion of this sort, but restricts it to object types precisely to avoid these problems. John Hughes ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Writing a counter function
I adjunt some code that i supose is what are you locking for. Is based in a previous message (by jefu on 13 of june) idea from the Haskell acumulator thread. the prueba function is the translation of your example. By the way, what's the purpose of this coding? (this is the type of question: ok, I have a hammer, now, for what kind of nail it is useful?) Cheers, Luis Michelena - Original Message - From: Shlomi Fish [EMAIL PROTECTED] To: Hannah Schroeter [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Saturday, June 29, 2002 12:58 PM Subject: Re: Writing a counter function On Sat, 29 Jun 2002, Hannah Schroeter wrote: Hello! On Sat, Jun 29, 2002 at 06:23:27PM +0300, Shlomi Fish wrote: [...] Actually, I'd like a more generalized counter. Something that would return both the number and a handler to add another number, which in turn would return the new sum and a new handler, etc. That's just what lazy lists are for. The handler thing is done automatically thanks to lazy evaluation. I.e. countFrom n = n : countFrom (n + 1) or just countFrom n = [n..] No. But I want to generate an irregular series, which I determine the intervals between two consecutive numbers myself. E.g: let (num1, next1) = (counter 5) (num2, next2) = (next1 100) (num3, next3) = (next2 50) in [num1,num2,num3] Will have the numbers [5, 105, 155]. Regards, Shlomi Fish Kind regards, Hannah. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Shlomi Fish[EMAIL PROTECTED] Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: [EMAIL PROTECTED] He who re-invents the wheel, understands much better how a wheel works. contador.hs Description: Binary data
Re: Writing a counter function
On Sun, 30 Jun 2002, Jon Fairbairn wrote: (snip) But there's the rub. It's not beautiful and it doesn't make much sense. I really wish we could get away from the How do I convert this imperative code snippet into Haskell questions into How do I solve this abstract problem? The question as originally posed didn't seem like it particularly needed something imperative though. For instance, the Perl isn't strongly imperative - it's largely just a list of declarations and functions (some anonymous) where you can think of the variables as being locally-declared constants. For instance, the first bit is very similar to, say, counter a = (a, \to_add - counter (a + to_add)) I think that's very different from asking people to translate into Haskell things where variables have their value change and whatever. Jon Cast's observation makes more sense to me - it's not a imperative/functional issue so much as a weak or strong typing issue. (snip) I guess that the last $next on the last line should have been $next3, but I'm not certain, and I certainly have no idea what the programme is /for/. Yes, I'm sure you're right there. Thanks very much for sharing the monadic approach - I was curious as to if monads could be used to break the recursion, and I didn't see anyone else mention that. I've certainly found Jon Cast's, John Hughes' and Andrew Bromage's articles interesting - it seems like this is a well-known issue and Haskell currently lies on an attractive point on the tradeoff between making things awkward and opening cans of worms. -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
lmichele wrote (on Sun, 30 Jun 2002 at 09:26): By the way, what's the purpose of this coding? (this is the type of question: ok, I have a hammer, now, for what kind of nail it is useful?) I would guess that something like the asked-for counter could be useful if one is allocating ranges of addresses to things, for example heap nodes when compiling a function body to instructions to build a graph. Why not have a monad m a = Int - (a,Int) which is a state monad plus the operation bump : Int - m Int bump k n = (n,n+k) Rgds, Peter Hancock ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
G'day all.
On Sun, Jun 30, 2002 at 01:51:56PM +0100, Peter G. Hancock wrote:
Why not have a monad m a = Int - (a,Int) which is a state monad plus
the operation bump : Int - m Int
bump k n = (n,n+k)
Oh, ye of insufficient genericity. We can do better than that...
import MonadTrans
class (Monad m, Enum i) = MonadCounter i m | m - i where
bump :: Int - m i
newtype CounterT i m a = CounterT { runCounterT :: i - m (a,i) }
instance (Monad m, Enum i) = Monad (CounterT i m) where
return a = CounterT $ \x - return (a, x)
m = k = CounterT $ \x - do
(a, x') - runCounterT m x
runCounterT (k a) x'
fail str = CounterT $ \_ - fail str
instance (Monad m, Enum i) = MonadCounter i (CounterT i m) where
bump k = CounterT $ \x -
let (next:_) = drop k [x..]
in return (x, next)
instance (Enum i) = MonadTrans (CounterT i) where
lift m = CounterT $ \x - do
a - m
return (a, x)
evalCounterT :: (Monad m, Enum i) = CounterT i m a - i - m a
evalCounterT m x = do
(a, _) - runCounterT m x
return a
-- Example code follows
main :: IO ()
main = evalCounterT count 0
count :: CounterT Int IO ()
count = do
x1 - bump 1
x2 - bump 5
x3 - bump 0
x4 - bump 1
lift (putStrLn $ show [x1,x2,x3,x4])
I'd better get back to work now.
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
On Sat, 29 Jun 2002, Mark Carroll wrote: On Sat, 29 Jun 2002, Shlomi Fish wrote: (snip) counter n = (n,(counter (n+1))) (snip) This doesn't work because you seem to be defining an infinitely deep tuple (1,(2,(3,(4,() which is naughty. I'm not really sure what alternative to suggest beyond [n .. ] without knowing more about what you are trying to do. Actually, I'd like a more generalized counter. Something that would return both the number and a handler to add another number, which in turn would return the new sum and a new handler, etc. Regards, Shlomi Fish -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Shlomi Fish[EMAIL PROTECTED] Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: [EMAIL PROTECTED] He who re-invents the wheel, understands much better how a wheel works. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
Hello! On Sat, Jun 29, 2002 at 06:23:27PM +0300, Shlomi Fish wrote: [...] Actually, I'd like a more generalized counter. Something that would return both the number and a handler to add another number, which in turn would return the new sum and a new handler, etc. That's just what lazy lists are for. The handler thing is done automatically thanks to lazy evaluation. I.e. countFrom n = n : countFrom (n + 1) or just countFrom n = [n..] Kind regards, Hannah. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
On Sat, 29 Jun 2002, Hannah Schroeter wrote: Hello! On Sat, Jun 29, 2002 at 06:23:27PM +0300, Shlomi Fish wrote: [...] Actually, I'd like a more generalized counter. Something that would return both the number and a handler to add another number, which in turn would return the new sum and a new handler, etc. That's just what lazy lists are for. The handler thing is done automatically thanks to lazy evaluation. I.e. countFrom n = n : countFrom (n + 1) or just countFrom n = [n..] No. But I want to generate an irregular series, which I determine the intervals between two consecutive numbers myself. E.g: let (num1, next1) = (counter 5) (num2, next2) = (next1 100) (num3, next3) = (next2 50) in [num1,num2,num3] Will have the numbers [5, 105, 155]. Regards, Shlomi Fish Kind regards, Hannah. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Shlomi Fish[EMAIL PROTECTED] Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: [EMAIL PROTECTED] He who re-invents the wheel, understands much better how a wheel works. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
Shlomi Fish wrote: No. But I want to generate an irregular series, which I determine the intervals between two consecutive numbers myself. E.g: let (num1, next1) = (counter 5) (num2, next2) = (next1 100) (num3, next3) = (next2 50) in [num1,num2,num3] Will have the numbers [5, 105, 155]. What do you mean by determine? You can write sequence = iterate step_counter 0 if the interval between successive numbers is determined by the current number, or sequence = map f [1..] if it's determined by the index in the sequence. or sequence = map snd $ iterate step_counter (0,-7) step_counter (a,b) = (a+1, f a b) if it depends on both. Jón -- Jón Fairbairn [EMAIL PROTECTED] 31 Chalmers Road [EMAIL PROTECTED] Cambridge CB1 3SZ+44 1223 570179 (after 14:00 only, please!) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
No. But I want to generate an irregular series, which I determine the intervals between two consecutive numbers myself. E.g: let (num1, next1) = (counter 5) (num2, next2) = (next1 100) (num3, next3) = (next2 50) in [num1,num2,num3] Will have the numbers [5, 105, 155]. Here's another not-exactly-what-you-wanted solution. :) If you don't mind changing your example to let (num1, next1) = out (counter 5) (num2, next2) = out (next1 100) (num3, next3) = out (next2 50) in [num1,num2,num3] then, you can do this: newtype Counter = MkCounter Int counter :: Int - Counter counter n = MkCounter n out :: Counter - (Int,Int - Counter) out (MkCounter n) = (n,MkCounter . (n +)) Sam Moelius ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
No. But I want to generate an irregular series, which I determine the intervals between two consecutive numbers myself. E.g: let (num1, next1) = (counter 5) (num2, next2) = (next1 100) (num3, next3) = (next2 50) in [num1,num2,num3] Will have the numbers [5, 105, 155]. Here's another not-exactly-what-you-wanted solution. :) If you don't mind changing your example to let (num1, next1) = out (counter 5) (num2, next2) = out (next1 100) (num3, next3) = out (next2 50) in [num1,num2,num3] then, you can do this: newtype Counter = MkCounter Int counter :: Int - Counter counter n = MkCounter n out :: Counter - (Int,Int - Counter) out (MkCounter n) = (n,MkCounter . (n +)) Sam Moelius ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Writing a counter function
On Sat, 29 Jun 2002, Samuel E. Moelius III wrote: (snip) Here's another not-exactly-what-you-wanted solution. :) (snip) Do any of the experimental extensions to Haskell allow a what-he-wanted solution? I couldn't arrange one in H98 without something having an infinitely-recursive type signature. I'm sure it would have been easy in Lisp, and he already gave a Perl equivalent, so I'm wondering if it could be at all sane for Haskell to allow such stuff and if Haskell is somehow keeping us on the straight and narrow by disallowing the exact counter that was originally requested. The beauty of his request was that it was so simple and seemed to make sense; I went ahead and tried to fulfill it before realising I couldn't do it either. -- Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
