- Haskell-Cafe - Haskell.org

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

15 Aug '02

[ moving to haskell-i18n(a)haskell.org ] > 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; Sorry, I thought you were just using ISO8859-1 as an example. > >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? I think we've lost track of the discussion here... I'll try to summarise. I think character encoding/decoding should be built-in to the I/O system. I also think there should be a low-level I/O interface that doesn't do any encoding, and high-level interfaces to the various encodings. Now, you can by all means specify the high-level I/O in terms of the low-level I/O + encodings, but I strongly suspect that implementing it that way will be expensive. Character I/O in Haskell is *already* very slow (see Doug Bagely's language shootout for evidence), and I don't want to add another factor of 2 or more to that. The point is that by building encoding into the I/O interface the implementor gets the opportunity to optimise. Cheers, Simon

1 0

RE: Analyzing Efficiency
by Simon Marlow 14 Aug '02

14 Aug '02

> I've come up with three different methods of approach to > solve the same > problem in haskell. I would like to compare the three in > terms of reductions, > memory usage, and overall big O complexity. > > What's the quickest way to gather these stats? I usually use the ghc > compiler, but also have hugs installed. The big O complexity > probably has to > be done by hand, but maybe there's a tool out there to do it > automagically. Apart from the "normal" ways (profiling, Unix 'time', GHC's +RTS -sstderr), here's another one I've been using recently: cachegrind. It's the wonderful cache profiling extension by Nick Nethercote that comes with Julian Seward's Valgrind. The great thing is that you don't even need to recompile the program - you just do 'cachegrind <program>', and it runs (very slowly) and outputs reliable cache statistics including how many instructions were executed. Get it from http://developer.kde.org/~sewardj/ Oh, it only works on Linux BTW. Cheers, Simon

1 0

Analyzing Efficiency
by Shawn P. Garbett 14 Aug '02

14 Aug '02

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I've come up with three different methods of approach to solve the same problem in haskell. I would like to compare the three in terms of reductions, memory usage, and overall big O complexity. What's the quickest way to gather these stats? I usually use the ghc compiler, but also have hugs installed. The big O complexity probably has to be done by hand, but maybe there's a tool out there to do it automagically. Shawn - -- 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) iD8DBQE9WU0BDtpPjAQxZ6ARAkTKAJ9qixYy5MT5QGyJ/95NGLNgVTECCQCfVVVV GHELk++jO8XzaWUbp/mb9Og= =MYjn -----END PGP SIGNATURE-----

2 1

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

14 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 14 Aug '02

14 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