- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Patterns for processing large but finite streams
by John Lato 01 Jul '11

01 Jul '11

After the list discussion, I'm surprised nobody mentioned Max Rabkin/Conal Elliott's blog posts on folds and zips. http://squing.blogspot.com/2008/11/beautiful-folding.html http://conal.net/blog/posts/enhancing-a-zip/ They develop a formalism for zipping functions on lists. Iteratee's `zip` set of functions are somewhat similar, but not quite the same. Specifically they still require multiple traversals of the data, but only over a bounded portion of it, so they're much more efficient. Of course you could combine the above patterns with iteratees by creating functions as above, then just running them with a 'fold'. John L. > From: Eugene Kirpichov <ekirpichov(a)gmail.com> > > Thanks but I'm afraid that's still not quite what I'm looking for; > guess I'll have to define my desire by my implementation - so once > it's ready I'll show the result to cafe :) > > 2011/7/1 Alexey Khudyakov <alexey.skladnoy(a)gmail.com>: > > On Fri, Jul 1, 2011 at 12:54 PM, Eugene Kirpichov <ekirpichov(a)gmail.com> > wrote: > >> Alexey, your definition of "mean" does not look like "liftS2 (/) sum > >> length" - you have to manually "fuse" these computations. > >> > > Well it was fused for numerical stability > > > >> I'm asking for a formalism that does this fusion automatically (and > >> guaranteedly). > >> > > Joining accumulators is quite straightforward. So is joining of initial > > state. Just creating a > >> joinAcc :: (acc1 -> x -> acc1) -> (acc2 -> x -> acc2) -> (acc1,acc2) -> > x -> (acc1,acc2) > >> joinAcc f1 f2 (s1,s2) x = (f1 s1 x, f2 s2 x) > > > > Still you have to handle them separately. > >> sum' = foldl (+) 0 > >> len ?= foldl (\n _ -> n+1) 0 > >> sumLen = foldl (joinAcc (+) (\n _ -> n+1)) (0,0) > > > > There is more regular approach but it only works with statistics. > > (function which do not depend on order of elements in the sample) > > For every statistics monoid for its evaluation could be constructed. > > For example sum: > >> newtype Sum a = Sum a > >> instance Num a => Monoid (Sum a) where > >> ? mempty = Sum 0 > >> ? mappend (Sum a) (Sum b) = Sum (a+b) > > > > Composition of these monoids becomes trivial. Just use > > > > > > I pursued this approach in monoid-statistics[1] package. > > It's reasonably well documented > > > > ?[1] http://hackage.haskell.org/package/monoid-statistics > > > >

1 0

Re: [Haskell-cafe] Patterns for processing large but finite streams
by John Lato 01 Jul '11

01 Jul '11

> > From: Eugene Kirpichov <ekirpichov(a)gmail.com> > Subject: [Haskell-cafe] Patterns for processing large but finite > streams > To: Haskell Cafe <haskell-cafe(a)haskell.org> > Message-ID: <BANLkTikdsvQ2Wv4WJR%2BQMuvksoav0kTqXw(a)mail.gmail.com> > Content-Type: text/plain; charset=ISO-8859-1 > > Hi, > > I'm rewriting timeplot to avoid holding the whole input in memory, and > naturally a problem arises: > > How to represent large but finite streams and functions that process > them, returning other streams or some kinds of aggregate values? > > Examples: > * Adjacent differences of a stream of numbers > * Given a stream of numbers with times, split it into buckets by time > of given width and produce a stream of (bucket, 50%,75% and 90% > quantiles in this bucket) > * Sum a stream of numbers > > Is this, perhaps, what comonads are for? Or iteratees? > This is exactly what iteratees are for. Specifically, enumeratees are stream transformers, iteratees are stream consumers, and enumerators are stream producers. Consider adjacent differences: Given the stream [a, b, c, d, e ....], you want to produce [b-a, c-b, d-c, e-d, ...] This is a stream transformer, so you need an enumeratee. Using iteratee, there are at least two obvious ways to produce it: 1) High-level, but probably not as good performance. Use Data.Iteratee.ListLike.roll > import Data.Iteratee as I > import Control.Applicative > > diff [x,y] = y-x > diff [x] = 0 > diffs = convStream (map diff <$> roll 2 1) > 2) somewhat explicit, probably better performance > import qualified Data.ListLike as LL > e' iter = do > h <- I.head > unfoldConvStream f h iter > where > f lastEl = do > c <- getChunk > if LL.null c > then return (lastEl, LL.empty) > else do > let h = LL.head c > t = LL.tail c > return (LL.last c, LL.cons (h-lastEl) (LL.zipWith (-) t (LL.init c))) either of these can be run by using an enumerator: *Main> enumPure1Chunk [1..10] (joinI $ e stream2list) >>= run [1,1,1,1,1,1,1,1,1,0] *Main> let e'2 = e' :: Enumeratee [Int] [Int] IO a *Main> enumPure1Chunk [1..10] (joinI $ e'2 stream2list) >>= run [1,1,1,1,1,1,1,1,1] I should optimize 'roll', it wouldn't be hard. Summing is easy; iteratee has "Data.Iteratee.ListLike.sum" built-in, but you could also use a fold. enumPure1Chunk is only useful for small amounts of data, but iteratee packages provide enumerators over files, handles, etc., as well as mechanisms by which you can create your own enumerators. The e' enumeratee is really just a model; I'd probably write one specific to whichever type of stream I wanted to work with. This one assumes a cheap 'cons', for example. For producing a stream of buckets, if the times are ordered it would be simple to do with Data.Iteratee.ListLike.breakE. If the times aren't ordered, I would probably use 'group' instead to collect a set number of samples. In my view, the biggest difference between iteratee and enumerator is the stream abstraction. Iteratee provides > I.Iteratee s m a where 's' is the stream type, e.g. [Int], String, ByteString, Vector Word8, etc. Although the library only processes a chunk at a time (where a chunk is a subsection of the stream), the type is that of the whole stream. Enumerator instead provides > E.Iteratee s m a here, 's' is the type of the chunk. Enumerator treats the stream as having type [s]. The implementations are different too, but ideally that would be hidden from most users. Although the iteratee implementation allows you to use >>= and $, whereas enumerator sometimes requires you to use >>== and $$. I think IterIO mostly follows the same type as Enumerator, although the implementation is again quite different. John

1 0

How to implement the mean function
by Ruohao Li 01 Jul '11

01 Jul '11

Hi guys, I just started learning some Haskell. I want to implement a mean function to compute the mean of a list. The signature of the function is: mean :: (Num a, Fractional b) => [a] -> b But when I implement this simple function, the compiler keep whining at me on type errors. I know this is wrong: mean xs = sum xs / length xs But how to get it right? Thanks.

5 7

Re: [Haskell-cafe] overloading show function
by Holger Siegel 30 Jun '11

30 Jun '11

Am 30.06.2011 um 20:23 schrieb Philipp Schneider: > On 06/30/2011 02:36 PM, Holger Siegel wrote: >> Am 29.06.2011 um 23:50 schrieb Philipp Schneider: >> >>> Hi cafe, >>> >>> in my program i use a monad of the following type >>> >>> newtype M a = M (State -> (a, State)) >>> >>> i use the monad in two different ways. The type variable "a" can be a >>> pair as in >>> >>> interp :: Term -> Environment -> M (Value,Environment) >>> >>> and it can be just a value as in >>> >>> type Environment = [(Name, Either Value (M Value))] >> Simple rule: Never return an environment! >> >> An environment contains local variable bindings, so no subcomputation will ever need to return its environment. I don't know anything about the language your program interprets, but I'm sure that you can rewrite function interp as >> >> interp :: Term -> Environment -> M Value >> >> The structure of the interpreter will become clearer and your problem will vanish. >> > Hello Holger, > > I'm giving two lambda interpreters. The first one is a call by value > interpreter, the second one a call by name interpreter which are > described in Philip Wadler's paper "The essence of functional > programming" page 4 and 12. Now my task is to write a lazy lambda > interpreter. The exercise is more playful than serious since Wadler's > call by value interpreter is, since written in lazy Haskell, already a > lazy lambda interpreter. (To get true call by value one would need to > force evaluations of the arguments with the seq function.) Hello Philipp, that's a nice exercise. > For both of Wadler's interpreters the type of the interpertation > function is: > interp :: Term -> Environment -> M Value > > Now to simulate lazy interpretation i need to do the following: Decide > is the value I need already evaluated or is it still a computation. In > the later case I need to evaluate it and save its value in the > environment. This is the reason I changed the type of the interpretation > function to: > interp :: Term -> Environment -> M (Value,Environment) But that won't work: After you have evaluated an entry of the environment, you store the resulting value but you throw away its updated environment. That means, you lose the results of all subcomputations instead of propagating them to all other copies of the environment. Consider the following expression: let x = big_computation in let y = x in y + x First, big_computation is bound to the name x, resulting in an environment [("x", big_computation)]. Then a closure consisting of this environment together with the right hand side 'x' is bound to the name y. Now y+x is evaluated: The closure is entered, and from its environment the content of x - a call to big_computation - is looked up. Now big_computation is evaluated and the result is bound to x in this environment. After that, this result is also returned as the value of y. But when returning from the evaluation of y, the environment with the updated value of x is lost and you have to re-evaluate it in order to calculate x+y! And that is why I say never return an environment. It is either wrong or unnecessary or the resulting semantics of the interpreter is hard to comprehend. In order to implement lazy evaluation correctly, you have to maintain some global state in which the thunks are updated. For example, your environment could bind IORefs that contain unevaluated thunks to variable names and update them when the thunk is evaluated. But then your interpreter has to run in the IO monad. By the way, do you already know Peter Sestoft's paper "Deriving a lazy abstract machine"? Cheers, Holger

2 3

ANNOUNCING: Hac PDX II - A Portland Haskell Hackathon
by Thomas DuBuisson 30 Jun '11

30 Jun '11

WHAT: A Haskell Hackathon WHEN: July 22-24 (Friday, Saturday, Sunday) 10:00 AM to 5:30 PM WHERE: Forth Avenue Building (FAB, 1900 SW 4th Ave) Room 10 Portland, Oregon 97201 WHERE, take 2: FAB10 is a small auditorium just inside the west most Harrison Street entrance. URL: http://haskell.org/haskellwiki/HacPDX-II WHAT, take 2: HacPDX-II is a Haskell Hackathon where beginners and experts alike can come to work on the Haskell projects of their choice - individually or in groups. If you don't have a project then never fear, come and pick one up or join a group (see the wiki for a list of projects). EQUIPMENT: You should bring a laptop with wireless (802.11). Ethernet is unavailable. Registration: Please RSVP by e-mailing thomas.dubuisson+hacpdx at gmail.com, as well as add your name to the attendees Wiki page (see above URL). Hope to see you there, Thomas

2 1

ANNOUNCE: mime-mail-ses 0.0.0
by Michael Snoyman 30 Jun '11

30 Jun '11

Hi all, I'd like to announce the first release of mime-mail-ses[1]. This provides easy integration between the mime-mail package[2] and Amazon's Simple Email Service. This package was written for the Haskellers website[3], purely because I despise setting up mail servers. There aren't many more features planned, though hopefully in the future it will integrate more closely with Aristid's aws package[4]. Also, a big thank you to Thomas DuBuisson for crypto-api[5] and Vincent Hanquez for cryptohash[6]. Those two packages make it very easy to write applications that require cryptographic authentication. Michael [1] http://hackage.haskell.org/package/mime-mail-ses [2] http://hackage.haskell.org/package/mime-mail [3] http://www.haskellers.com/ [4] http://hackage.haskell.org/package/aws [5] http://hackage.haskell.org/package/crypto-api [6] http://hackage.haskell.org/package/cryptohash

1 0

overloading show function
by Philipp Schneider 30 Jun '11

30 Jun '11

Hi cafe, in my program i use a monad of the following type newtype M a = M (State -> (a, State)) i use the monad in two different ways. The type variable "a" can be a pair as in interp :: Term -> Environment -> M (Value,Environment) and it can be just a value as in type Environment = [(Name, Either Value (M Value))] now in any case when i print the monad, i just want to print the value and never the environment. More specific i want to use somthing like the following instance (Show a,Show b) => Show (M (a,b)) where show (M f) = let ((v,_), s) = f 0 in "Value: " ++ show v ++ " Count: " ++ show s instance Show a => Show (M a) where show (M f) = let (v, s) = f 0 in "Value: " ++ show v ++ " Count: " ++ show s however this gives me the following error message: Overlapping instances for Show (M (Value, Environment)) arising from a use of `print' Matching instances: instance (Show a, Show b) => Show (M (a, b)) -- Defined at /home/phil/code/haskell/vorlesung/ue09/ue09-3c3.hs:78:10-42 instance Show a => Show (M a) -- Defined at /home/phil/code/haskell/vorlesung/ue09/ue09-3c3.hs:82:10-29 In a stmt of an interactive GHCi command: print it Any ideas how to fix it? Thanks! Philipp

5 7

what if two package contains same module?
by 吴兴博 30 Jun '11

30 Jun '11

it seems that cabal install different into different folders. if two package contains same module name, can they all exist? since cabal have no "remvoe" or "uninstall". how can I hide some packages? Cheers! ---------------- 吴兴博 Wu Xingbo

4 3

Haskell Weekly News: Issue 188
by Daniel Santa Cruz 30 Jun '11

30 Jun '11

Welcome to issue 188 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of June 19 to 25, 2011. It was brought up in cafe this week that some would prefer to see full links in the text version of the mailing list as opposed to the shortened links. The reason behind using shortened links is that the newsletter becomes pretty much unreadable with long links in a plain text buffer. In an effort to accommodate both needs, I'm trying a new format for links. One that includes shorter links embedded throughout the newsletter, and the full reference at the bottom of the text. Let me know what you think! If you are reading this on a mobile device, or you would just rather see the HTML version, point your browser to: http://contemplatecode.blogspot.com/2011/06/haskell-weekly-news-issue-188.h… Announcements Alex Mason wrote in to remind us that AusHac2011 (the Australasian Haskell Hackathon) will be held on July 8-10, at UNSW in Sydney. "If you are an Australian haskell hacker, enthusiast, newbie or professional, we would love to see you there." [2] http://goo.gl/d0SXy Florent Becker announced the release of darcs 2.8 beta 1, with many new beta features. Give it a world and let the devs know how things are working! [3] http://goo.gl/rq3DM Quotes of the Week * <[~functor(a)zygohistomorphic-prepromorphism.endofunctor.org] has joined #haskell * kmc: actually, C++'s "typename" keyword is inspired by INTERCAL's "PLEASE" * Toxaris: #haskell delivers a massively multiprogrammer online functional programming (MMOFP) experience * sully: although I'm switching to haskell more and more just on practical grounds * mauke: the greek letter lambda is an imperfect approximation of the symbol \ * Cale: The trouble with sarcasm is that in order for it to really be effective, the listener has to know what the speaker knows. Otherwise, it's indistinguishable from ignorance. Top Reddit Stories * Haskell's evaluation isn't magic. Domain: netsuperbrain.com, Score: 42, Comments: 33 On Reddit: [4] http://goo.gl/jD8jM Original: [5] http://goo.gl/31pyt * Superclass equalities are now supported Domain: hackage.haskell.org, Score: 40, Comments: 16 On Reddit: [6] http://goo.gl/5PuUh Original: [7] http://goo.gl/XhrMR * Free Monads for Less (Part 1 of 3): Codensity Domain: comonad.com, Score: 35, Comments: On Reddit: [8] http://goo.gl/mqkDi Original: [9] http://goo.gl/9eWLr * Renewed LambdaCube 3D engine, Bullet bindings and Stunts example Domain: just-bottom.blogspot.com, Score: 33, Comments: 2 On Reddit: [10] http://goo.gl/UsP59 Original: [11] http://goo.gl/YR3sH * A new design for haskell.org Domain: chrisdone.com, Score: 31, Comments: 47 On Reddit: [12] http://goo.gl/044JZ Original: [13] http://goo.gl/Hvivh * Free Monads for Less (Part 2 of 3): Yoneda Domain: comonad.com, Score: 25, Comments: On Reddit: [14] http://goo.gl/K6fI9 Original: [15] http://goo.gl/bjV5f * Free Monads for Less (Part 3 of 3): Yielding IO Domain: comonad.com, Score: 24, Comments: On Reddit: [16] http://goo.gl/pKXUR Original: [17] http://goo.gl/EDxzo * Snap Framework v0.5.1 released Domain: snapframework.com, Score: 20, Comments: 2 On Reddit: [18] http://goo.gl/sKsqq Original: [19] http://goo.gl/Chk6j * Comparing FRP to RDP (Reactive Demand Programming) Domain: awelonblue.wordpress.com, Score: 19, Comments: 2 On Reddit: [20] http://goo.gl/0wEgx Original: [21] http://goo.gl/B4dYs * Haskell eDSL Tutorial - Shared expenses Domain: lpenz.org, Score: 18, Comments: 11 On Reddit: [22] http://goo.gl/6yf5j Original: [23] http://goo.gl/t14Xs Top StackOverflow Questions * How do you write data structures that are as efficient as possible in GHC? votes: 26, answers: 2 Read on SO: [24] http://goo.gl/cj18P * How does seq force functions? votes: 15, answers: 1 Read on SO: [25] http://goo.gl/f1TX8 * I/O in Haskell is Functional? votes: 14, answers: 5 Read on SO: [26] http://goo.gl/ZT0HQ * Exponentiation in Haskell votes: 12, answers: 4 Read on SO: [27] http://goo.gl/ueo1A * How to compile a resource into a binary in Haskell? votes: 12, answers: 4 Read on SO: [28] http://goo.gl/mxDPV * Haskell Heap Issues with Parameter Passing Style votes: 12, answers: 2 Read on SO: [29] http://goo.gl/b2m10 * Functor is for (a -> b) -> (f a -> f b), what is for (Category c) => c a b -> c (f a) (f b) ? votes: 12, answers: 1 Read on SO: [30] http://goo.gl/Usv7I * Better way to write the following program in Haskell votes: 12, answers: 7 Read on SO: [31] http://goo.gl/Dn7Xj About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz References 1. http://haskell.org 2. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18670 3. http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/90496 4. http://www.reddit.com/r/haskell/comments/i4k3j/haskells_evaluation_isnt_mag… 5. http://netsuperbrain.com/blog/posts/haskells-evaluation-isnt-magic 6. http://www.reddit.com/r/haskell/comments/i6ftr/superclass_equalities_are_no… 7. http://hackage.haskell.org/trac/ghc/ticket/2715#comment:18 8. http://www.reddit.com/r/haskell/comments/i7sy0/free_monads_for_less_part_1_… 9. http://comonad.com/reader/2011/free-monads-for-less/ 10. http://www.reddit.com/r/haskell/comments/i6qi5/renewed_lambdacube_3d_engine… 11. http://just-bottom.blogspot.com/2011/06/renewed-lambdacube-bullet-bindings-… 12. http://www.reddit.com/r/haskell/comments/i9183/a_new_design_for_haskellorg/ 13. http://chrisdone.com/designs/haskell/ 14. http://www.reddit.com/r/haskell/comments/i7v5r/free_monads_for_less_part_2_… 15. http://comonad.com/reader/2011/free-monads-for-less-2/ 16. http://www.reddit.com/r/haskell/comments/i7vho/free_monads_for_less_part_3_… 17. http://comonad.com/reader/2011/free-monads-for-less-3/ 18. http://www.reddit.com/r/haskell/comments/i3odg/snap_framework_v051_released/ 19. http://snapframework.com/blog/2011/06/19/snap-0.5.1-released 20. http://www.reddit.com/r/haskell/comments/i4i5c/comparing_frp_to_rdp_reactiv… 21. http://awelonblue.wordpress.com/2011/05/21/comparing-frp-to-rdp/ 22. http://www.reddit.com/r/haskell/comments/i8ylw/haskell_edsl_tutorial_shared… 23. http://lpenz.org/articles/hedsl-sharedexpenses 24. http://stackoverflow.com/questions/6432284/how-do-you-write-data-structures… 25. http://stackoverflow.com/questions/6442019/how-does-seq-force-functions 26. http://stackoverflow.com/questions/6399702/i-o-in-haskell-is-functional 27. http://stackoverflow.com/questions/6400568/exponentiation-in-haskell 28. http://stackoverflow.com/questions/6402158/how-to-compile-a-resource-into-a… 29. http://stackoverflow.com/questions/6429085/haskell-heap-issues-with-paramet… 30. http://stackoverflow.com/questions/6445501/functor-is-for-a-b-f-a-f-b-what-… 31. http://stackoverflow.com/questions/6476319/better-way-to-write-the-followin…

1 0

Re: [Haskell-cafe] [Haskell-beginners] Understanding category theory
by Jack Henahan 30 Jun '11

30 Jun '11

Derp, forgot to CC the Cafe. Which ones have you read already? It's difficult to make recommendations without knowing what's already off the table. Additionally, don't be put off if it takes a lot of effort to figure anything out. Math textbooks and so on are unlike any other textbook. It's not unusual to spend a day (or several days) trying to digest a single page of material unless you have a strong mathematical background (or even if you do). This is especially true in the more abstract disciplines (and if there's anything more abstract than category theory, I don't think I've yet encountered it). On Jun 29, 2011, at 8:26 PM, Christopher Howard wrote: > Would anyone recommend a particular book or tutorial to help me understand category theory? I've tried reading a few tutorials i've googled, but even the "beginner" ones are very difficult and seem to assume a lot. > > Sent from my HTC > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners ==== "Computer Science is no more about computers than astronomy is about telescopes." -- Edsger Dijkstra ====

1 0