August 2002 - Haskell-Cafe

RE: Text in Haskell: a second proposal
by Ashley Yakeley 13 Aug '02

13 Aug '02

At 2002-08-13 04:13, Simon Marlow wrote: >That depends what you mean by efficient: these functions represent an >extra layer of intermediate list between the handle buffer and the final >[Char], and furthermore they don't work with partial reads - the input >has to be a lazy stream gotten from hGetContents. For ISO-8859-1 each Char is exactly one Word8, so surely it would work fine with partial reads? decodeCharISO88591 :: Word8 -> Char; encodeCharISO88591 :: Char -> Word8; decodeISO88591 :: [Word8] -> [Char]; decodeISO88591 = fmap decodeCharISO88591; encodeISO88591 :: [Char] -> [Word8]; encodeISO88591 = fmap encodeCharISO88591; >> A monadic stream-transformer: >> >> decodeStreamUTF8 :: (Monad m) => m Word8 -> m Char; >> >> hGetChar h = decodeStreamUTF8 (hGetWord8 h); >> >> This works provided each Char corresponds to a contiguous block of >> Word8s, with no state between them. I think that includes all the >> standard character encoding schemes. > >This is better: it doesn't force you to use lazy I/O, and when >specialised to the IO monad it might get decent performance. The >problem is that in general I don't think you can assume the lack of >state. For example: UTF-7 has a state which needs to be retained >between characters, and UTF-16 and UTF-32 have an endianness state which >can be changed by a special sequence at the beginning of the file. Some >other encodings have states too. But it is possible to do this in Haskell... The rule for the many functions in the standard libraries seems to be "implement as much in Haskell as possible". Why is it any different with the file APIs? -- Ashley Yakeley, Seattle WA

1 0

Newbie question on "statefullness"
by Alex Peake 13 Aug '02

13 Aug '02

I am new to Haskell. I want to do something very simple (I thought) but got lost in the world of Monads. I want to implement something like the C idea of: n += i So how does one doe this in Haskell? Thanks, Alex

8 11

Re: Analyzing Efficiency
by Shawn P. Garbett 13 Aug '02

13 Aug '02

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Tuesday 13 August 2002 01:37 pm, you wrote: > > I would like to compare the three in terms of reductions, memory > > usage, and overall big O complexity. > > I wouldn't use number of reductions as a guide if I was you. Number of reductions does make a difference in this case, because it's a simple test problem with three equivalent implementations (in the same compiler). Nothing to create confusion like a system call, well actually all three solutions must call a set of IO calls in the same order. So I think it would make a good baseline comparison. I do agree that it's not a good general measurement of efficiency, and really doesn't reflect the scalability of the solution either (whereas big O notation would). Thanks for the heads up though. The other tips and hints you gave me are exactly what I was looking for. No I just need a huge data set to pump into so it does a significant amount of garbage collection, and memory management... Shawn Garbett - -- You're in a maze of twisty little statements, all alike. Public Key available from http://www.garbett.org/public-key -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) iD8DBQE9WVM5DtpPjAQxZ6ARAn2XAJ98Y4jNmnCocHzHEFpUM/vN3kTGmACfTnkf Vk3m8x1OYHGyckskR4DDKQo= =OWav -----END PGP SIGNATURE-----

1 0

RE: Text in Haskell: a second proposal
by Simon Marlow 13 Aug '02

13 Aug '02

> At 2002-08-09 03:26, Simon Marlow wrote: > > >Why combine I/O and {en,de}coding? Firstly, efficiency. > > Hmm... surely the encoding functions can be defined efficiently? > > decodeISO88591 :: [Word8] -> [Char]; > encodeISO88591 :: [Char] -> [Word8]; -- uses low octet of > codepoint > > You could surely define them as native functions very efficiently, if > necessary. That depends what you mean by efficient: these functions represent an extra layer of intermediate list between the handle buffer and the final [Char], and furthermore they don't work with partial reads - the input has to be a lazy stream gotten from hGetContents. I don't want to be forced to use lazy I/O. > A monadic stream-transformer: > > decodeStreamUTF8 :: (Monad m) => m Word8 -> m Char; > > hGetChar h = decodeStreamUTF8 (hGetWord8 h); > > This works provided each Char corresponds to a contiguous block of > Word8s, with no state between them. I think that includes all the > standard character encoding schemes. This is better: it doesn't force you to use lazy I/O, and when specialised to the IO monad it might get decent performance. The problem is that in general I don't think you can assume the lack of state. For example: UTF-7 has a state which needs to be retained between characters, and UTF-16 and UTF-32 have an endianness state which can be changed by a special sequence at the beginning of the file. Some other encodings have states too. Cheers, Simon

1 0

Fw: Modification of State Transformer
by Scott J. 12 Aug '02

12 Aug '02

----- Original Message ----- From: "Scott J." <jscott(a)planetinternet.be> To: "Shawn P. Garbett" <Shawn(a)Garbett.org> Sent: Monday, August 12, 2002 9:04 PM Subject: Re: Modification of State Transformer > I 'm sorry, > > What I meant was discussion about the state transformer ST s a itself. And > how it works. What does mean the second inner forall loop and so on. I can't > find explanations of this in the Haskell library. > > Regards > > Scott > ----- Original Message ----- > From: "Shawn P. Garbett" <Shawn(a)Garbett.org> > To: "Scott J." <jscott(a)planetinternet.be> > Cc: <haskell-cafe(a)haskell.org> > Sent: Monday, August 12, 2002 4:19 PM > Subject: Re: Modification of State Transformer > > > > -----BEGIN PGP SIGNED MESSAGE----- > > Hash: SHA1 > > > > On Sunday 11 August 2002 07:26 pm, Scott J. wrote: > > > Hi, > > > > > > I invite you then to explain what happens with every step. > > > > > > The use of "forall" is misleading and fast to be misunderstood: I > mention > > > here the inner forall's. > > > > > > Thx > > > > > > Scott > > > > This list is great. The implementation in the ST module solves the > > > > problem and I understand how it works. > > > > > > > > Shawn > > > > Given the level of detailed explanations to date, I don't see the point. > But > > I'll go ahead and do so anyway, by summarizing what I've learned from the > > previous posts. > > > > I had read the example in Bird'd book on state transformers. The > definition > > of state however was a fixed type in the examples. Wanting to extend the > > definition and make it more general I was trying to figure out how to > modify > > the type. > > > > Bird's definition was: > > newtype St a = MkSt (State -> (a,State)) > > type State = type > > > > I had attempted to extend the type as follows > > newtype St a s = MkSt (s -> (a,s)) > > > > This died in the compiler when declaring this type as an instance of > Monad: > > instance Monad St where > > return x = MkSt f where f s = (x,s) > > p >>= q = MkSt f where f s = apply(q x) s' > > where (x,s') = apply p s > > ghc returned the following (referencing the instance line): > > Couldn't match `*' against `* -> *' > > Expected kind: (* -> *) -> * > > Inferred kind: (* -> * -> *) -> * > > When checking kinds in `Monad St' > > In the instance declaration for `Monad St' > > > > When a type constructor has an argument it has a type of `* -> *'. > > When a type constructor has two arguments it has a type of `* -> * -> *'. > > This construction of the type can be extended to n arguments by having the > > number of `->' match the n arguments of type and the `*' be n+1. > > > > The class definition of Monad contains the following: > > class Monad m where > > return :: a -> m a > > (>>=) :: m a -> (a -> m b) -> m b > > > > > > So the class of St a s needs reduction from `* -> * -> *' to `* -> *' to > fit > > the single argument type constructor of the Monad class. By using (St a) > > which causes the type constructor to be of type `(* -> *) -> *'. Since > `(* -> > > *)' can be used as `*', by creation of another type. This because > equivalent > > to `* -> *'. > > > > The only thing left is reversing the order so that the result type is of > the > > correct form in the Monad usage. I.e, in my initial ordering the `return' > of > > the Monad would end up returning something of type `s' which is not > > particularly useful, since type `a' is the desired return type from the > > transformer. > > > > So the corrected version of State becomes: > > newtype St s a = MkSt (s -> (a, s)) > > > > instance Monad (St s) where > > ... > > > > Shawn Garbett > > - -- > > You're in a maze of twisty little statements, all alike. > > Public Key available from http://www.garbett.org/public-key > > -----BEGIN PGP SIGNATURE----- > > Version: GnuPG v1.0.7 (GNU/Linux) > > > > iD8DBQE9V8P4DtpPjAQxZ6ARAq0VAJ9toEiEm+d58vgbKEofzXBISyXrEACfasbc > > eaEg2zVi9y90vk+fXKGSrt0= > > =OrwN > > -----END PGP SIGNATURE----- > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > >

2 1

Re: Modification of State Transformer
by Jon Cast 12 Aug '02

12 Aug '02

"Shawn P. Garbett" <listman(a)garbett.org> wrote: > I'm trying to modify Richard Bird's state transformer. The example > in his book (_Introduction_to_Functional_Programming_using_Haskell_) > has State defined as a explicit type. > I.e. Here's the relevant snippet: > -- State transformer definition > newtype St a = MkSt (State -> (a, State)) > type State = Int > -- State transformer applied to state > apply :: St a -> State -> (a, State) > apply (MkSt f) s = f s > -- State monad > instance Monad St where > return x = MkSt f where f s = (x,s) > p >>= q = MkSt f where f s = apply (q x) s' > where (x, s') = apply p s > ----------------------------------------- > What I want is something like this, so that the state transformer > has a generic state type: Btw: This has already been done, in GHC: see the ST module in GHC's library <http://www.haskell.org/ghc/docs/latest/html/base/Control.Monad.ST.html>. To answer your specific question, though: > newtype St a s = MkSt (s -> (a, s)) These are in the wrong order (see below); you want: > newtype St s a = MkSt (s -> (a, s)) > apply :: St a s -> s -> (a, s) > apply (MkSt f) s = f s Again, s/St a s/St s a/. > instance Monad St where > return x = MkSt f where f s = (x,s) > p >>= q = MkSt f where f s = apply (q x) s' > where (x, s') = apply p s > ----------------------------------------------------------- > The trouble occurs on the instance line > Couldn't match `*' against `* -> *' > Expected kind: (* -> *) -> * > Inferred kind: (* -> * -> *) -> * > When checking kinds in `Monad St' > In the instance declaration for `Monad St' > Failed, modules loaded: none. Right. The problem here is that St is a type constructor with two arguments (i.e., of kind (* -> * -> *)), whereas Monad wants a type constructor with one argument (i.e., of kind (* -> *)). Hence the error. This is the same type of error you'd get if you tried to declare an instance for `Eq Tree', where `Tree' is a standard (polymorphic) BST. The way you solve that is to instantiate `Eq (Tree a)', and it's the same thing here: instantiate `Monad (St s)'. Of course, you need to switch the order of the arguments to St first (as done above), so Haskell knows `s' is a the state type, not the result type. HTH Jon Cast

3 3

Re: Newbie question on "statefullness"
by Ashley Yakeley 12 Aug '02

12 Aug '02

At 2002-08-11 23:48, I wrote: >>I want to implement something like the C idea of: >>n += i >> >>So how does one doe this in Haskell? > > do { > val <- readIORef n; > writeIORef n (val + i); > }; Or even... modifyIORef n ((+) i); -- Ashley Yakeley, Seattle WA

1 0

Re: Newbie question on "statefullness"
by Ashley Yakeley 12 Aug '02

12 Aug '02

At 2002-08-11 17:36, Alex Peake wrote: >I want to implement something like the C idea of: >n += i > >So how does one doe this in Haskell? do { val <- readIORef n; writeIORef n (val + i); }; -- Ashley Yakeley, Seattle WA

1 0

Haskell-Cafe -- confirmation of subscription -- request 321501
by Cyril Baratoff 09 Aug '02

09 Aug '02

1 0

Combining type constraints
by Andrew J Bromage 08 Aug '02

08 Aug '02

G'day all. I have a large number of functions all of which use the same set of type constraints, such as: > foo :: (Monad m, Ord t, Show t) => ... Ideally, I'd like to combine them into one typeclass. At the moment, I'm using the equivalent of: > class (Monad m, Ord t, Show t) => Constraints m t where { } > instance (Monad m, Ord t, Show t) => Constraints m t where { } > foo :: (Constraints m t) => ... This requires undecidable instances. Is there a way to do this that doesn't require non-98 features apart from multi-parameter type classes? If not, is there an argument for a language construction which supports this idiom, analogous to type synonyms, except for type classes? Cheers, Andrew Bromage

1 0