- Haskell-Cafe - Haskell.org

Decorating a list of strings
by Steve Schafer 03 Nov '06

03 Nov '06

I have a list of text strings: ["Alice", "Bob", "Cindy", "Bob", "Bob", "Dave", "Cindy"] As you can see, some of the strings occur only once; others appear two or more times. I would like to end up with a new list, according to the following rules: 1) If a string occurs only once in the original list, then that string appears unchanged in the new list. 2) If a string occurs more than once in the original list, then each occurrences of that string is "decorated" with a numerical suffix indicating its relative position among its peers. In the case of the above list, the result of applying these rules would be: ["Alice", "Bob:1", "Cindy:1", "Bob:2", "Bob:3", "Dave", "Cindy:2"] So, how do we do this? The straightforward approach is to traverse the list twice, once to build a table of repeat counts for the different strings, and a second time to generate the new list, based on the old list plus the table of repeat counts. Of course, it's possible to streamline this into a single traversal by building up a list of thunks at the same time as the table of repeat counts is generated, and then to resolve those thunks by applying them in one fell swoop to the table. But while this does _conceptually_ streamline the problem, it doesn't offer any practical improvement; it takes at least as much processing effort to resolve the thunks as it would to make a second pass through the list. Can we do better? I can't think of a way to do better, and my gut feeling is that there isn't one (in general, it's impossible to know whether the first element of the new list will be "Alice" or "Alice:1" until the entire original list has been traversed), but I thought I'd put the question out to the community to see if anyone had any brilliant insights. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

3 3

Towards an IO-Comonad that preserves referential integry (was: "comonads, io" Jan 02, 2003)
by Sven Biedermann 03 Nov '06

03 Nov '06

Dear Haskellers, The OI Comonad in Richard Kieburtz' paper does break referential integrity, but he worte, that the implementation is just something "...to experiment with". In this papers he states, that a real OI needs special properties. For instance enableOI needs "...to have the effect of copying pointers to currently accessible IO resources, in effect duplicating the current IO environment." So, I wrote a simple OI-Comonad for stdin/stdout only, that preserves referential integrity. At least, my reasoning and the tests I made didn't reveal anything different. The code and some explanations are presented at the end of this mail. Haskellers: Could you review the solution, please? Does it really preserves referential integrity? Or am I completely wrong? Do you have any suggestions on generalizing the idea? I would be glad to hear from you! Best regards Sven Biedermann ---------------------------------------------------------------- The implementation is based on two ideas: 1) The OI outside world is modeled an infinite structure (OIReality) that keeps track effects created in the outside world. All "futures" of a reality at a point of "time" are remembered in a lazy fashion. So, if one probes on referential integrity, the structure will be re-iterated through, playing back already computed results. If a reality at some point of "time" isn't referenced any more, that reality will be reclaimed by the garbage collector. The following statement is an example, that no space leaks occur as long as a specific reality isn't remembered (stdPutStr builds on basic stdPutChar using the standard operators .>> and =>>): extract $ mkOI 'x' .>> (cycle ['A'..'z']) =>> oiPutStr Amazingly, extract $ mkOI 'x' .>> (cycle ['A'..'z']) =>> oiPutStrLn produces a space leak, because the implementation isn't lazy enough, yet. 2) The OI-Comonad is a pointer to the current reality, together with the value, that can be extracted from OI. Whenever an OI ist rememberable by the user, the pointer will be duplicated. This is crucial for referential integrity. Comain, as defined by Andrew Bromage in : comain :: OI a -> () comain w = extract (w .>> show (a,b) =>> oiPutStrLn) where a = extract (w .>> () =>> oiGetChar) b = extract (w .>> () =>> oiGetChar) now works as intended and delivers, if 'x' is typed in on standard input: ('x','x') "a = ..." runs on reality w, yielding 'x' . "b = ..." is just a play back of "a = ...". "extract (w.>> show (a,b) =>> stdPutStrLn)" is another future of w, which just prints ('x','x'). module SimpleOI where import Control.Monad.Instances import System.IO.Unsafe import Data.Char import Data.IORef -------------------------------------- -- copied from http://www.eyrie.org/~zednenem/2004/hsce/ class Functor w => Comonad w where extract :: w a -> a duplicate :: w a -> w (w a) extend :: (w a -> b) -> (w a -> w b) extend f = fmap f . duplicate duplicate = extend id -- | 'fmap' defined in terms of 'extend' liftW :: Comonad w => (a -> b) -> (w a -> w b) liftW f = extend (f . extract) -- | 'extend' with the arguments swapped. Dual to '>>=' for monads. (=>>) :: Comonad w => w a -> (w a -> b) -> w b (=>>) = flip extend -- | Injects a value into the comonad. (.>>) :: Comonad w => w a -> b -> w b w .>> b = extend (\_ -> b) w -- end of copy ------------------------------------- data OIReality = OIReality GetChar [PutChar] Char data GetChar = GetChar Char OIReality data PutChar = PutChar () OIReality constructReality :: Char -> OIReality constructReality c = let r = OIReality (constructGet r) (constructPuts r) c in r constructGet :: OIReality -> GetChar constructGet r = let c = unsafePerformIO $ seq r getChar in GetChar c (constructReality c) constructPut :: OIReality -> Char -> PutChar constructPut r c = let v = unsafePerformIO $ seq r $ putChar c in PutChar v (constructReality c) constructPuts :: OIReality -> [PutChar] constructPuts r = map (constructPut r.chr) [0..255] nextGetCharReality :: OIReality -> OIReality nextGetCharReality (OIReality (GetChar c r) _ _) = r nextPutCharReality :: Char -> OIReality -> OIReality nextPutCharReality c (OIReality _ puts _) = let PutChar v r = puts !! (ord c) in seq v r data OIComonad a = OI (IORef OIReality) a -- extract OI _ a = a instance Functor OIComonad where fmap f (OI ref a) = seq a $ OI (unsafeDuplicateRef ref) (f a) -- too many seq's at the moment instance Comonad OIComonad where duplicate w = fmap (const w) w extract (OI _ a) = a mkOI :: Char -> OIComonad Char mkOI c = OI (unsafePerformIO $ newIORef $ constructReality c) c oiGetChar :: OIComonad a -> Char oiGetChar (OI ref _) = unsafePerformIO $ do { modifyIORef ref nextGetCharReality; OIReality _ _ c <- readIORef ref; return (c) } oiPutChar :: OIComonad Char -> () oiPutChar (OI ref c) = unsafePerformIO $ do { modifyIORef ref (nextPutCharReality c); OIReality _ _ d <- readIORef ref; -- not!? modified without further read return $ seq d ()} unsafeDuplicateRef :: IORef OIReality -> IORef OIReality unsafeDuplicateRef ref = unsafePerformIO $ do { r <- readIORef ref; newIORef r; } oiPutStrLn w = extract $ w =>> oiPutStr .>> '\n' =>> oiPutChar -- space leak if input string is suffiently long -- too many seqs in code oiPutStr w = extract $ oiPutStrS w .>> () oiPutStrS :: OIComonad String -> OIComonad String oiPutStrS w = case (extract w) of [] -> w (c:cs) -> oiPutStrS (w .>> c =>> oiPutChar .>> cs) oiGetLine = "t.b.d. using oiGetChar" -- adapted from http://www.mail-archive.com/haskell-cafe@haskell.org/ msg02408.html comain w = extract (w .>> show (a,b) =>> oiPutStr) where a = extract (w .>> () =>> oiGetChar) b = extract (w .>> () =>> oiGetChar) {- Original from http://www.mail-archive.com/haskell-cafe@haskell.org/ msg02408.html -- Bootstrap into the OI comonad main :: IO () main = return $! comain stdOI -- The following are the OI functions which we use. -- stdGetChar :: OI () -> Char -- stdPutStrLn :: OI String -> () comain :: OI a -> () comain w = coeval (w .>> show (a,b) =>> stdPutStrLn) where a = coeval (w .>> () =>> stdGetChar) b = coeval (w .>> () =>> stdGetChar) -}

3 3

Very Small Program
by Bernie Pope 03 Nov '06

03 Nov '06

On 02/11/2006, at 9:56 PM, ajb(a)spamcop.net wrote: > G'day all. > > Quoting Bernie Pope <bjpop(a)csse.unimelb.edu.au>: > >> This is a weird example of a pattern binding, and it is surprising >> (to me) that the syntax is valid. > > Maybe. But you wouldn't balk at this: > > numzeroes xs = sum [ 1 | 0 <- xs ] > > ...even if you wouldn't naturally express it that way. Patterns like > this are useful in places other than lets. I'd find it more > surprising > if lets were treated as a special case. > >> In this case you are defining the function which is bound to the >> variable called "+". > > Though thanks to n+k patterns, this is well-understood to be a > confusing and controversial case. > >> One would normally expect to see at least one variable inside the >> pattern on the >> left-hand-side of a pattern binding (otherwise what point would there >> be to the >> definition?). > > If the pattern is demanded (as it may well be in a list comprehension > generator, do block generator or a lambda), then it can be very > useful. > The programmer is asking for an error/empty list/monad "fail" if the > conformality check fails. I agree with what you say. When I said "pattern binding", I was using the terminology of the Haskell Report, which means only declarations of the form "pat = exp". Generator statements and lambdas are a different story, as you rightly point out. Nonetheless, I still believe that it is surprising for "pattern bindings" that this syntax is allowed, since there doesn't seem to be any purpose to them. (A cursory glance at the Report suggests that this kind of pattern binding is allowed). Then again, since the bindings are benign, maybe one could argue that it is better to have one less rule in the language definition? Then again, such a declaration could be the sign of a buggy program, and it might be better to give a compile time error. Cheers, Bernie.

1 0

Very Small Program
by Jason Dagit 02 Nov '06

02 Nov '06

Hello, I just found it (in ghci and hugs) that this is a valid haskell program: let 0 = 1 in 0 This program evaluates to 0 (to my surprise). I expected something similar to how this works: let { 1 + 1 = 3; 3 + 1 = 7 } in 1 + 1 + 1 Where you get 7. So, if the 0 is not used as an identifier (ie, defining a function or name of a value), then why doesn't this count as a parse error? And, why didn't I get to locally redefine it? Thanks, Jason

5 4

Fwd: [Haskell-cafe] Class
by Slavomir Kaslev 02 Nov '06

02 Nov '06

---------- Forwarded message ---------- From: Slavomir Kaslev <slavomir.kaslev(a)gmail.com> Date: Nov 2, 2006 10:47 AM Subject: Re: [Haskell-cafe] Class To: Daniel Fischer <daniel.is.fischer(a)web.de> On 11/2/06, Daniel Fischer <daniel.is.fischer(a)web.de> wrote: > Am Donnerstag, 2. November 2006 00:06 schrieb Slavomir Kaslev: > > Hello. > > > > I am new to Haskell and I am going through "Haskell: The craft of > > functional programming". I am trying to grasp haskell's classes and > > instances, so here is slightly modified code from the book: > > > > class Show a => Visible a where > > toString :: a -> String > > toString = show > > size :: a -> Int > > size = length . show > > > > instance Visible a => Visible [a] where > > toString = concat . map toString > > size = foldl (+) 0 . map size > > > > vSort :: (Visible a, Ord a) => [a] -> String > > vSort = toString . List.sort > ^^^^^^^ > my ghc complained that List.sort is not in scope, did you import Data.List as > List? Yes, I did imported Data.List. My mistake for forgetting to add it in the post. > > > > s = vSort [1..3] > > > > Unfortunetly in ghc it gives the following type error: > > Ambiguous type variable `a' in the constraints: > > `Visible a' arising from use of `vSort' at d:/tmp.hs:83:4-8 > > `Enum a' arising from the arithmetic sequence `1 .. 3' at > > d:/tmp.hs:83:10-15 > > `Num a' arising from the literal `3' at d:/tmp.hs:83:14 > > `Ord a' arising from use of `vSort' at d:/tmp.hs:83:4-8 > > Probable fix: add a type signature that fixes these type variable(s) > > Failed, modules loaded: none. > > > > As you can see, Visible is nothing more than an adapter to the Show > > class. How I got thing so far, [1..3] :: (Num a, Enum a) => [a], has a > > Show instance so does class Num (which 'subclasses' Show). Therefore, > > I can't see any reason why toString function can't call show from > > those instances. > > First problem: class Visible has no instances yet, so even if you disambiguate > the type by writing e.g. > s = vSort [1 :: Int .. 3], you'll get an error message: > Visible.hs:20:4: > No instance for (Visible Int) > arising from use of `vSort' at Visible.hs:20:4-8 > Probable fix: add an instance declaration for (Visible Int) > In the definition of `s': s = vSort ([1 :: Int .. 3]) Visible 'subclasses' Show. Doesn't this mean that Visible should be defined for all types with Show instances? I don't want to write Visible Int, if ghc has already defined a Show Int instance. > > And the second problem: > The typechecker has no means of determining which type 1 should have. > By virtue of the fact that numeric literals are overloaded in Haskell, it has > type Num a => a. The use of enumFromTo adds the Enum a constraint and vSort > adds Ord and Visible, however there may be many types satisfying these > constraints and ghc says it's up to you to select one. > And even if there is only one instance of Visible declared, ghc (nor, as far > as I know, any other Haskell implementation) won't select that because there > might, somewhere in a long-forgotten directory, lie a module dormant in which > another instance satisfying all constraints is declared. > To sum up: instance selection is left to the user, the compiler does only type > _inference_. Often that determines which instance fits, but sometimes you > have to give an expression type signature to tell the compiler what to > choose. I agree with second problem you pointed out. Thanks for mentioning it. -- Slavomir Kaslev -- Slavomir Kaslev

2 1

Class
by Slavomir Kaslev 02 Nov '06

02 Nov '06

Hello. I am new to Haskell and I am going through "Haskell: The craft of functional programming". I am trying to grasp haskell's classes and instances, so here is slightly modified code from the book: class Show a => Visible a where toString :: a -> String toString = show size :: a -> Int size = length . show instance Visible a => Visible [a] where toString = concat . map toString size = foldl (+) 0 . map size vSort :: (Visible a, Ord a) => [a] -> String vSort = toString . List.sort s = vSort [1..3] Unfortunetly in ghc it gives the following type error: Ambiguous type variable `a' in the constraints: `Visible a' arising from use of `vSort' at d:/tmp.hs:83:4-8 `Enum a' arising from the arithmetic sequence `1 .. 3' at d:/tmp.hs:83:10-15 `Num a' arising from the literal `3' at d:/tmp.hs:83:14 `Ord a' arising from use of `vSort' at d:/tmp.hs:83:4-8 Probable fix: add a type signature that fixes these type variable(s) Failed, modules loaded: none. As you can see, Visible is nothing more than an adapter to the Show class. How I got thing so far, [1..3] :: (Num a, Enum a) => [a], has a Show instance so does class Num (which 'subclasses' Show). Therefore, I can't see any reason why toString function can't call show from those instances. Can someone please enlighten my (still) C++ thinking head? -- Slavomir Kaslev

3 3

Basic Binary IO
by Nuno Pinto 02 Nov '06

02 Nov '06

Hi all! Today i was reading System.IO and didn't manage to understand how it works just by reading it. I looked the internet for some help on this, but only "advanced" information is available. Can anyone show me how to use openBinaryFile ? Just an example, like opening file "somefile" and separating it into something that can be edited in the code (like 8 bit words) then go to word nr12 and edit the last bit? Thanks! NP _________________________________________________________________ Search from any Web page with powerful protection. Get the FREE Windows Live Toolbar Today! http://www.toolbar.live.com

3 2

Re: [Haskell-cafe] What is the best way to preserve the order of a list (RESOLVED)
by John Ky 02 Nov '06

02 Nov '06

Thanks Stefan, -John On 11/1/06, Stefan Holdermans <stefan(a)cs.uu.nl> wrote: > > John, > > > My question is, how do I preserve the ordering of entities in my > > list and still be able to assign the proper order values to each > > entity? Is there an efficient way to do this? How else might I > > improve my orderByPriority algorithm. > > Straightforwardly, you could do it like this: > > import List (sortBy) > > type Priority = Int > type Order = Int > > order :: [Priority] -> [(Priority, Order)] > order = unlabel . sortOnLab . assignOrder . sortOnPrio . label > where > label = zip [0 ..] > unlabel = map snd > sortOnLab = sortBy (\(l, _) (m, _) -> compare l m) > sortOnPrio = sortBy (\(_, p) (_, q) -> compare p q) > assignOrder = \xs -> zipWith (\(l, p) o -> (l, (p, o))) xs [0 ..] > > For instance: > > > order [5, 2, 3, 7] > [(5,2),(2,0),(3,1),(7,3)] > > HTH, > > Stefan >

1 0

Post mesg
by Farida Mishra 02 Nov '06

02 Nov '06

Hi i would like to post mesg this list --------------------------------- Everyone is raving about the all-new Yahoo! Mail.

2 1

there's a monster in my Haskell!
by Andrew Pimlott 01 Nov '06

01 Nov '06

To boost the popularity of Scheme, Felleisen has argued for renaming "lambda" to "something cool, such as Funster".[1] Likewise, Haskell intimidates newcomers with the arcane term "monad". Peyton Jones's hopeful campaign to replace it with "warm fuzzy thing"[2] has so far produced few results. Inspired by Felleisen, and in the spirit of Halloween, I offer a new alternative: Meet "monsters", your computational companions in the land of lazy functional programming. To illustrate this proposal, I present here a gentle introduction to monsters. Monsters come in great variety, each type having its own special powers. But, as noted by Elmo[3], they are alike in an essential way. All monsters are capable of devouring values: devour :: Monster m => a -> m a The result of "devour x" is simply a monster that has ingested the value "x". Most monsters have a weakness and can be slain, liberating some ingested values or producing some other result. The instrument of demise varies, as do the possible outcomes, so this function is particular to a monster. If SomeMonster always yields a single value upon its demise, we would have slay :: SomeMonster a -> a The compassionate (and fastidious) programmer defers the gruesome (and messy) slaying while making use of the monster's special powers. But how to get at the monster's values short of that macabre act? Fortunately, monsters gladly contribute their values towards the creation of more monsters: (>>=) :: Monster m => m a -> (a -> m b) -> m b (>>=) should be read as the monster on the left expelling values through its rows of teeth and over its tongue at the function on the right. (Its pronunciation is a sort of bestial hissing that is difficult to describe; when you say it correctly, the terminal may become slightly moist.) Monsters range from the tame to the tumultuous, but we cannot let them run entirely amok. All therefore must obey the "monster laws". For instance, the regurgitation law states that immediately after devouring a value, a monster expels the same value: devour x >>= k === k x We have still seen none of the promised special powers. For that, we must look at a particular monster. The Either monster is defined as data Either a b = Trick a | Treat b This monster devours Treats, but if it doesn't get a Treat, it can play a Trick: playTrick :: t -> Trick t a playTrick t = Trick t This monster is commonly used as follows: takeFood :: Food -> Either Mischief Food takeFood Apple = playTrick eggHouse takeFood Raisins = playTrick tpTree takeFood CandyCorn = devour CandyCorn The divine among monsters is the mysterious and awesome IO. Its powers are vast, perhaps limitless, and beginners are taught that it cannot be slain. Like poisoned candy and release dates, this is of course a myth. The pure of spirit may, after meditation at the altar of referential transparency, cast the spell :: IO a -> a (When you are prepared to call this function, its name will be revealed.) The ST monster can be slain without esoteric ritual: slay :: (forall s. ST s a) -> a Yet philosophers whisper that there is something otherworldly about it, a kinship with IO. Eavesdropping on their debates, I hear the words "phantom type", but that gives me the chills so I leave them. [1] http://permalink.gmane.org/gmane.comp.lang.lightweight/3427 [2] http://research.microsoft.com/~simonpj/papers/haskell-retrospective/ [3] http://muppet.wikia.com/wiki/We%27re_All_Monsters

6 5