- Haskell-Cafe - Haskell.org

generic filter through MonadPlus
by Jason Dusek 22 May '09

22 May '09

It seems reasonable that filter should be generic. The underlying container need only support some kind of traversal, a zero element and a concatenation that eliminates zeroes. A `Monad` provides traversal via `join` and `fmap`; the remaining qualities are satisfied by `MonadPlus`. I've put together an implementation of `filter` for `MonadPlus` that works well enough for lists (though it presents somewhat greater obstacles to efficient compilation). I'm not sure whether `filter` is important enough to warrant its own generics package -- it's one of many collection operations that need to be generified. I'd like to know what folks think about the use of `MonadPlus` in this case. -- Jason Dusek |...an implementation of `filter`...| http://github.com/jsnx/genfil/blob/246026b975ec13587186681b7b346ae1e440d0c9…

2 1

Re: A problem with par and modules boundaries...
by John Lato 22 May '09

22 May '09

Hi Mario, It looks like the parallelize function is getting inlined when it's in the same file, but not when it's in a separate file. Adding a {-# INLINE parallelize #-} pragma to the module with parallelize recovers all the performance for me. You could probably see exactly what's happening in more detail by going through the Core output. John Lato > Message: 23 > Date: Thu, 21 May 2009 22:59:51 -0400 > From: Mario Bla?evi? <mblazevic(a)stilo.com> > Subject: [Haskell-cafe] A problem with par and modules boundaries... > To: <haskell-cafe(a)haskell.org> > Message-ID: <.1242961191@magma.ca> > Content-Type: text/plain; charset="utf-8" > > I'll cut to the chase. The short program below works perfectly: when I compile it > with -O2 -threaded and run with +RTS -N2 command-line options, I get a nearly 50% > real-time improvement: > > $ time ./primes-test +RTS -N2 > 5001 > > real 0m9.307s > user 0m16.581s > sys 0m0.200s > > However, if I move the `parallelize' definition into another module and import > that module, the performance is completely lost: > > $ time ./primes-test +RTS -N2 > 5001 > > real 0m15.282s > user 0m15.165s > sys 0m0.080s > > I'm confused. I know that `par` must be able work across modules boundaries, > because Control.Parallel.Strategies is a module and presumably it works. What am > I doing wrong? > > >> module Main where >> >> import Control.Parallel >> import Data.List (find) >> import Data.Maybe (maybe) >> >> --import Parallelizable >> parallelize a b = a `par` (b `pseq` (a, b)) >> >> test :: Integer -> Integer -> Integer >> test n1 n2 = let (p1, p2) = parallelize >> (product $ factors $ product [1..n1]) >> (product $ factors $ product [1..n2]) >> in p2 `div` p1 >> >> factors n = maybe [n] (\k-> (k : factors (n `div` k))) >> (find (\k-> n `mod` k == 0) [2 .. n - 1]) >> >> main = print (test 5000 5001) >

1 0

haskellnet
by Robert Wills 22 May '09

22 May '09

Hello, Yesterday I found myself wanting to clear out a spam-ridden pop account without downloading all the messages. Rather than just using Python's poplib, I thought I might look for a haskell solution and came across Haskellnet: http://darcs.haskell.org/SoC/haskellnet/ I ended up spending much of the afternoon getting it to compile and much of last night trying to get the pop library to actually work (the 'strip' method produced exceptions). It was a good learning experience (this was helpful: http://donsbot.wordpress.com/2007/11/14/no-more-exceptions-debugging-haskel…) I'm writing here because I'm wondering whether it would be worthwhile putting it up on hackage? From searching this list, there seem to have been a few times when people have stumbled across it but got frustrated when it didn't compile. If so, what's the protocol? Is the original author, Jun Mukai, still around? Thanks, Rob

2 2

Putting unit tests in cabal files (Was Re: [Haskell-cafe] HUnit)
by Magnus Therning 22 May '09

22 May '09

On Fri, May 22, 2009 at 12:13 AM, Vasili I. Galchin <vigalchin(a)gmail.com> wrote: > Hello, > > I have some code with several test cases that use HUnit. I added hunit > as one of my cabal dependencies but cabal complained with: > > Setup: At least the following dependencies are missing: > hutil -any > > What am I doing incorrectly? Would you mind posting your .cabal file too? The reson I'm asking is that I've so far _never_ put any information about unit tests or quickcheck tests in my .cabal file, simply because I don't want the executables to be picked up by automatic package converters such as cabal2arch. Instead I have a makefile for building my test programs. If you have some way of keeping information about building of tests in your .cabal I'd be very interested in seeing it. /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe

2 2

HUnit
by Vasili I. Galchin 22 May '09

22 May '09

Hello, I have some code with several test cases that use HUnit. I added hunit as one of my cabal dependencies but cabal complained with: Setup: At least the following dependencies are missing: hutil -any What am I doing incorrectly? Thanks, Vasili

3 3

ANN: TxtSushi 0.1
by Keith Sheppard 22 May '09

22 May '09

Hello Haskell Cafe I have released the first version of TxtSushi which is a collection of command line utils (written in haskell of course) for processing tab-delimited and CSV files. It includes a util for doing SQL SELECTs on flat files. This is my first haskell project and feedback of all kinds is appreciated. Home Page: http://www.keithsheppard.name/txt-sushi Darcs Repository: http://patch-tag.com/r/txt-sushi/home Issue Tracking: http://code.google.com/p/txt-sushi I would like to say thanks to the haskell-beginners contributors, the author of "Learn you a Haskell" and the author of the parsec library all of which were very helpful. Regards Keith

3 6

Function Returning Type?
by jrw4 22 May '09

22 May '09

I wrote this function as I am just learning Haskell. What it does is it generates a list of all rational numbers between 0 and 1, but I only have it show the first 20. rationals n :: Integer -> String rationals n = (putStr . unlines . map show) (take n (nub [x % y | y <- [1..], x <- [1..y], x < y])) Now my problem is the type declaration, the first line. I get the error "Invalid type signature". I googled this error and I was not able to find out why it is giving it to me. I have also tried: rationals n :: Integer -> [Ratio] but it gives me the same error. Please someone point me in the right direction. Thanks. -- View this message in context: http://www.nabble.com/Function-Returning-Type--tp23658819p23658819.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

5 5

ANN: feed2twitter 0.2 & hackage2twitter 0.2.1
by Tom Lokhorst 22 May '09

22 May '09

To all the cool kids using the Twitter (and to anyone else): I'm happy to announce the first release of feed2twitter. Build on top of the excellent feed and hs-twitter packages, feed2twitter sends posts from a news feed to Twitter. The hackage2twitter executable is build on top of the feed2twitter library. It `tweets' the releases of new Hackage-packages. In the 3 days it has been running, it has already posted 70+ releases: http://twitter.com/Hackage - Tom Lokhorst http://hackage.haskell.org/cgi-bin/hackage-scripts/package/feed2twitter http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hackage2twitter

5 6

Re: [Haskell-cafe] Haskell in 3 Slides
by Kalman Noel 22 May '09

22 May '09

Joe Fredette schrieb: > 3-4 slides imply 3-4 topics, so the question is what are the 3-4 biggest > topics in haskell? I would think they would be: > > * Purity/Referential Transparency > * Lazy Evaluation > * Strong Typing + Type Classes > * Monads If the goal is to be able to talk about different examples of Haskell code in the rest of the presentation, the big topic I'd choose would be called »How function definitions look like in Haskell«. Kalman

3 2

Haskell philosophy question
by Vasili I. Galchin 22 May '09

22 May '09

Hello, I am confused between Haskell as delineated in the Haskell Report VS ghc "pragmas" which extend Haskell beyond the Haskell Report. I am sure I am not the first to ask. Caveat: on my part, I am not against innovation/extensions, but I don't like to see language "bloat". This is not a negative/pegorative statement .... just a challenging one. Kind regards, vasili

6 6

Re: Re: [Haskell-cafe] what's the definition of "satisfy" and "<?>" ?
by Lee Duhem 21 May '09

21 May '09

On Thu, May 21, 2009 at 6:48 PM, z_axis <z_axis(a)163.com> wrote: > Sorry! I am a haskell newbie. then i will have a look at > Text.ParserCombinators.Parsec.Char Don't forget to CC your reply to the list, so other people on the thread will see your reply. lee

1 0

ANN: EsotericBot 0.0.1
by spoon＠killersmurf.com 21 May '09

21 May '09

Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/esotericbot See the homepage for online copy of README and example configuration file: http://www.killersmurf.com/projects/esotericbot Esotericbot is a sophisticated, lightweight IRC bot, written in Haskell. Esotericbot launches sub-processes to respond to commands issued by users over IRC. Why would you use esotericbot? For lambdabot-4.2.2.1: spoon@utensil:~/esotericbot$ ps e v PID TTY STAT TIME MAJFL TRS DRS RSS %MEM COMMAND 23433 pts/3 Sl+ 0:00 0 8228 84855 33476 1.6 lambdabot 15040 pts/5 S+ 0:00 0 2171 28804 3292 0.1 ./esotericbot I'm not insinuating that lambdabot sucks in any way, ( for lambdabot is most excellent ) however, my hope is that esotericbot could attain equal functionality through plugins, whilst maintaining its small memory footprint. Esotericbot is small, designed to run on a server with limited memory - typically running at under 5mb of private memory. Features: * Advanced memory and time management options, utilizing POSIX resource management. For example, the memory used by all child processes, can be limited - commands be queued until the memory usage has dropped. * Privileged channel operator commands ( Currently, can be disabled and enabled by channel operators, without kicking. ) * Easy to add new plugins. A C library is included to make writing new plugins/adapting programs in C easy. * Set up through a configuration file. * Multiple channels. * Multi-threaded * Lightweight, typically running at under 5mb of private memory. Cons: * POSIX memory management, process forking, and chroot means that Esotericbot is POSIX only. * Esotericbot is, due to the libraries and extensions used, restricted to being compiled by the Glorious Glasgow Haskell Compiler.

2 1

ghc ./configure stalls on docbook DTD
by Dan 21 May '09

21 May '09

Hi, Not sure if this is the right place to ask. GHC 6.10.3 source dist: ./configure takes about 10 minutes to look for DocBook DTD and another 10 to look for DocBook XSL directory. I was writing this e-mail thinking it had completely crashed. Any reason why it's so ridiculously slow? A look at 'top' says the CPU is mostly idle during this time, but xmllint is running. Mac OS X uname -a: Darwin 9.6.0 Darwin Kernel Version 9.6.0: Mon Nov 24 17:37:00 PST 2008; root:xnu-1228.9.59~1/RELEASE_I386 i386 CookBook:ghc-6.10.3 dan$ ./configure checking build system type... i386-apple-darwin9.6.0 checking host system type... i386-apple-darwin9.6.0 checking target system type... i386-apple-darwin9.6.0 Canonicalised to: i386-apple-darwin [blah blah blah] checking for xmllint... /usr/bin/xmllint checking for DocBook DTD... (blocks for ages)

4 3

what's the definition of "satisfy" and "<?>" ?
by z_axis＠163.com 21 May '09

21 May '09

I cannot understand the following code very well as i donot know the definition of "satisfy" and "<?>". -- | Case-insensitive variant of Parsec's 'char' function. caseChar :: Char -> GenParser Char a Char caseChar c = satisfy (\x -> toUpper x == toUpper c) -- | Case-insensitive variant of Parsec's 'string' function. caseString :: String -> GenParser Char a () caseString cs = mapM_ caseChar cs <?> cs Would somebody mind to explain the code in detail ? Sincerely!

3 2

Re: [Haskell-cafe] showing a user defined type
by michael rice 21 May '09

21 May '09

Thanks for the extra patience. What does "unsafe" mean? From my perspective, you had a perfectly good chain_take function fun chain_take(0,_) = nil | chain_take(n,Link(i,f)) = i :: chain_take(n-1,f(i)) - chain_take(5,always1(6)); val it = [1,1,1,1,1] : int list Putting aside weird_chain_take for now, what, if anything, is unsafe about chain_take? Michael --- On Wed, 5/20/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "michael rice" <nowgate(a)yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, haskell-cafe(a)haskell.org Date: Wednesday, May 20, 2009, 2:21 PM Actually, I was saying that "chain" already emulates laziness, just in a somewhat unsafe way, as demonstrated by weird_take. In Haskell you'd probably just write > ints :: Int -> [Int] > ints n = [n..] and be done with it. -- ryan On Wed, May 20, 2009 at 9:41 AM, michael rice <nowgate(a)yahoo.com> wrote: > OK, I think I understand. You were explaining how ML could be made to > emulate Haskell laziness using streams, ala Scheme type delayed evaluation, > so it's kind of like you were explaining a question I hadn't quite asked > yet, which maybe explains my puzzlement, I hope. > > Also, though my understanding of both Haskell and ML syntax is still > rudimentary, I did catch an error in your definition of chain_take: the > first arg of the cons should be i rather than n. > > I'm still going through your code and may have further questions. > > Thanks for your input. > > Michael > > > --- On Wed, 5/20/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > > From: Ryan Ingram <ryani.spam(a)gmail.com> > Subject: Re: [Haskell-cafe] showing a user defined type > To: "michael rice" <nowgate(a)yahoo.com> > Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, > haskell-cafe(a)haskell.org > Date: Wednesday, May 20, 2009, 4:12 AM > > (Apologies for my mutilation of ML syntax, I don't completely know the > language) > > Consider the ML type int list, and this function to build one: > > broken_repeat :: int -> int list > broken_repeat n = Cons(n, broken_repeat(n)) > > This function is recursive, and doesn't terminate; it tries to build > an infinite list of ints and your computer runs out of heap and/or > stack trying to evaluate it. > > But the "chain" type doesn't have this problem; you can see it as an > int list that gets evaluated "on demand": > > repeat :: int -> chain > repeat(n) = Link(n, repeat) > > always1 :: int -> chain > always1(_) = Link(1, always1) > > chain_take :: int * chain -> int list > chain_take (0,_) = Nil > chain_take (n,Link(i,f)) = Cons(n, chain_take(n-1, f(i))) > > But, nothing in the "chain" type stops you from passing a different > value to the function in the link: > > weird_take :: int * int * chain -> int list > weird_take (0,_,_) = Nil > weird_take (n,v,Link(i,f)) = Cons(i, weird_take(n-1,v,f(v))) > > Now, it's possible that chain_take returns the same list for two > different "chain" inputs, but weird_take might return different lists > depending on how f is implemented. For example: > chain_take(5, repeat(1)) = [1,1,1,1,1] > chain_take(5, always1(1) = [1,1,1,1,1] > > weird_take(5, 2, repeat(1)) = [1,2,2,2,2] > weird_take(5, 2, always1(1)) = [1,1,1,1,1] > > One way to fix this is to embed the "state" of the chain in the closure > itself. > > So, in ML, the type > unit -> X > is commonly called a "thunk"; it can be used to delay computation > until later, until it's demanded, just like any lazy value in Haskell. > > f :: unit -> Int > f () = 1 > > This f isn't very useful; it's basically the same as "1". But > consider this type: > > datatype stream = Stream of (int * (unit -> stream)) > > stream1 () = Stream(1, stream1) > > stream_take :: int*stream -> int list > stream_take(0,_) = Nil > stream_take(n,Stream(i,f)) = Cons(i, stream_take(n-1, f())) > > Now there is no way to pass a different value like we did in > weird_take; there's only (). > > The difference is that the state gets embedded in the closure for the thunk: > > stream_ints :: int -> (unit -> stream) > stream_ints = fun n => fun () => Stream(n, stream_ints(n+1)) > > What you are doing here is encoding laziness; the Haskell version of this > type: > >> data Stream = Stream !Int Stream -- !Int means the Int value is strict >> stream1 = Stream 1 stream1 >> stream_ints n = Stream n (stream_ints(n+1)) > >> stream_take :: Int -> Stream -> [Int] >> stream_take 0 _ = [] >> stream_take n (Stream x xs) = x : stream_take (n-1) xs > > No extra (\() -> ...) thunk is required, due to laziness :) > > -- ryan > > On Tue, May 19, 2009 at 4:25 PM, michael rice <nowgate(a)yahoo.com> wrote: >> Hi Ryan, >> >> I'm afraid you've lost me. Maybe if you showed how this would be used in >> ML >> I would get the picture. >> >> Michael >> >> --- On Tue, 5/19/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: >> >> From: Ryan Ingram <ryani.spam(a)gmail.com> >> Subject: Re: [Haskell-cafe] showing a user defined type >> To: "michael rice" <nowgate(a)yahoo.com> >> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, >> haskell-cafe(a)haskell.org >> Date: Tuesday, May 19, 2009, 2:40 PM >> >> On Tue, May 19, 2009 at 7:07 AM, michael rice <nowgate(a)yahoo.com> wrote: >>> A little further along in "The Little MLer" the ints function is replaced >>> by >>> other functions like primes and fibs, which also return Links: >>> >>> fun primes(n) >>> = if is_prime(n+1) >>> then Link(n+1,primes) >>> else primes(n+1) >>> >>> fun fibs(n)(m) >>> = Link(n+m,fibs(m)) >>> >>> which are passed to chain_item: >>> >>> fun chain_item(n,Link(i,f)) >>> = if eq_int(n,1) >>> then i >>> else chain_item(n-1,f(i)) >>> >>> which can be called to request the nth (12th) prime number beginning at >>> 1. >>> >>> - chain_item(12,primes(1)); >>> GC #0.0.0.1.3.61: (1 ms) >>> val it = 37 : int >>> - >>> >>> So I guess the answer to your question about whether the function is ever >>> called with a different value may be, yes. >> >> Actually, it's not calling it with another value; notice that >> chain_item calls f(i), with i coming directly from the chain. >> Consider this alternate definition: >> (I'm not sure the syntax is exactly right, but you get the idea) >> >> datatype chain = >> Link of (int * ( unit -> chain )) >> >> fun intsFrom(n) = fun unit => (n, intsFrom (n+1)) >> fun ints(n) = intsFrom n () >> >> Now you *can't* call the function embedded in the link with another value. >> >> fun chain_item(n,Link(i,f)) >> = if eq_int(n,1) >> then i >> else chain_item(n-1,f unit) >> >> And this type for "chain" is almost the same as [Int] in Haskell, due >> to laziness. >> >> -- ryan >> >> > >

2 1

Tree traversal / stack overflow
by Matthew Eastman 21 May '09

21 May '09

Hi, I've been writing some code to calculate the stretch factor of a tree of points. What it means is that for every node in a tree (lets call it 'pivot'), I have to traverse the same tree (lets call each node 'current') and sum d_t(pivot, current) / d(pivot, current) for each node, where d_t is the tree path distance between two nodes and d is the Euclidean distance. What I've been doing is traversing the tree, pivoting up each node into the root position, and calculating the stretch factor for each new tree. ex. +===+ +===+ +===+ | 1 | | 2 | | 3 | +===+ .---+===+----. +===+ / / | | \ \ +---+ +---+ +---+ +---+ +---+ +---+ | 2 | ---> | 3 | | 4 | | 5 | | 1 | ---> | 2 | etc. .+---+. +---+ +---+ +---+ +---+ .+---+. / | \ / | \ +---+ +---+ +---+ +---+ +---+ +---+ | 3 | | 4 | | 5 | | 4 | | 5 | | 1 | +---+ +---+ +---+ +---+ +---+ +---+ The code I have right now works great on point sets of size ~10,000, but when I go up much higher things start to go wrong. I start hitting stack overflows, so I increased the stack size. For ~100,000 points though, running the code with +RTS -sstderr -K128m it chugged along for over an hour and then died with a stack overflow. The stats said it spent 50 seconds MUT time and 5300 seconds (almost 90 minutes!) GC time, which seems odd. The performance has been really good for lower numbers of points, but the professor I'm working for wants to handle over a million points later on. I've only been writing Haskell for a year, and I'm not quite sure how to rewrite this so that it won't blow the stack, since I'm pretty sure this kind of tree traversal can't be done with tail calls (I would love to proved wrong, though!). Any help would be appreciated. Thanks, Matt module ASF ( averageStretchFactor ) where import Data.Tree import Data.Foldable (foldr') type Point = (Double,Double) square :: Double -> Double square x = x * x dist :: Point -> Point -> Double dist (x1,y1) (x2,y2) = sqrt (square (x2 - x1) + square (y2 - y1)) add :: Tree a -> Tree a -> Tree a add (Node p sts) t = Node p (t:sts) -- Calculate the average stretch factor of a tree of size n. It's the sum of -- the average stretch factor of each node in the tree, divided by n choose 2 -- (the number of possible pairs of points in in a tree of size n) averageStretchFactor :: Tree Point -> Double -> Double averageStretchFactor tree n = stretchRotations tree / (n * (n - 1) / 2) -- Calculate the stretch factor of a tree. -- The stretch of two points is the tree path distance between the two points -- divided by the euclidean distance between the two points. The stretch factor -- of a tree is the sum of the stretches between the root and every other node -- in the tree. stretchFactor :: Tree Point -> Double stretchFactor (Node point sts) = stretch 0 point sts where stretch _ _ [] = 0 stretch d p ((Node p' sts'):ts) = pd / ed + stretch pd p' sts' + stretch d p ts where pd = d + dist p p' -- path distance ed = dist point p' -- euclidean distance -- Calculate the stretch factor of every point by pulling up each node in the -- tree to the root position. Note that the overall structure of the tree -- doesn't change, we're essentially just traversing the tree and calculating -- the stretch factor of each node by pretending we're at the root. stretchRotations :: Tree Point -> Double stretchRotations tree = rotate tree [] where rotate tree@(Node p sts) path = stretchFactor (foldr' add tree path) + pivot [] sts path p pivot _ [] _ _ = 0 pivot ls (r:rs) path p = rotate r (Node p (ls ++ rs) : path) + pivot (r:ls) rs path p ./main 10000 +RTS -sstderr -K128m ASF = 22.441 1,298,891,896 bytes allocated in the heap 20,191,904 bytes copied during GC 3,107,116 bytes maximum residency (7 sample(s)) 47,480 bytes maximum slop 8 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 2471 collections, 0 parallel, 0.06s, 0.07s elapsed Generation 1: 7 collections, 0 parallel, 0.03s, 0.03s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 13.05s ( 13.18s elapsed) GC time 0.09s ( 0.11s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 13.14s ( 13.29s elapsed) %GC time 0.7% (0.8% elapsed) Alloc rate 99,506,082 bytes per MUT second Productivity 99.3% of total user, 98.2% of total elapsed ./main 100000 +RTS -sstderr -K128m Stack space overflow: current size 128000000 bytes. Use `+RTS -Ksize' to increase it. 33,097,322,168 bytes allocated in the heap 3,004,248,280 bytes copied during GC 704,391,196 bytes maximum residency (29 sample(s)) 67,420,196 bytes maximum slop 1731 MB total memory in use (14 MB lost due to fragmentation) Generation 0: 62561 collections, 0 parallel, 5364.16s, 5619.83s elapsed Generation 1: 29 collections, 0 parallel, 4.50s, 48.73s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 49.85s ( 78.94s elapsed) GC time 5368.66s (5668.56s elapsed) EXIT time 0.00s ( 7.88s elapsed) Total time 5418.51s (5747.56s elapsed) %GC time 99.1% (98.6% elapsed) Alloc rate 663,930,946 bytes per MUT second Productivity 0.9% of total user, 0.9% of total elapsed

1 1

Re: [Haskell-cafe] showing a user defined type
by michael rice 21 May '09

21 May '09

OK, I think I understand. You were explaining how ML could be made to emulate Haskell laziness using streams, ala Scheme type delayed evaluation, so it's kind of like you were explaining a question I hadn't quite asked yet, which maybe explains my puzzlement, I hope. Also, though my understanding of both Haskell and ML syntax is still rudimentary, I did catch an error in your definition of chain_take: the first arg of the cons should be i rather than n. I'm still going through your code and may have further questions. Thanks for your input. Michael --- On Wed, 5/20/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "michael rice" <nowgate(a)yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, haskell-cafe(a)haskell.org Date: Wednesday, May 20, 2009, 4:12 AM (Apologies for my mutilation of ML syntax, I don't completely know the language) Consider the ML type int list, and this function to build one: broken_repeat :: int -> int list broken_repeat n = Cons(n, broken_repeat(n)) This function is recursive, and doesn't terminate; it tries to build an infinite list of ints and your computer runs out of heap and/or stack trying to evaluate it. But the "chain" type doesn't have this problem; you can see it as an int list that gets evaluated "on demand": repeat :: int -> chain repeat(n) = Link(n, repeat) always1 :: int -> chain always1(_) = Link(1, always1) chain_take :: int * chain -> int list chain_take (0,_) = Nil chain_take (n,Link(i,f)) = Cons(n, chain_take(n-1, f(i))) But, nothing in the "chain" type stops you from passing a different value to the function in the link: weird_take :: int * int * chain -> int list weird_take (0,_,_) = Nil weird_take (n,v,Link(i,f)) = Cons(i, weird_take(n-1,v,f(v))) Now, it's possible that chain_take returns the same list for two different "chain" inputs, but weird_take might return different lists depending on how f is implemented. For example: chain_take(5, repeat(1)) = [1,1,1,1,1] chain_take(5, always1(1) = [1,1,1,1,1] weird_take(5, 2, repeat(1)) = [1,2,2,2,2] weird_take(5, 2, always1(1)) = [1,1,1,1,1] One way to fix this is to embed the "state" of the chain in the closure itself. So, in ML, the type unit -> X is commonly called a "thunk"; it can be used to delay computation until later, until it's demanded, just like any lazy value in Haskell. f :: unit -> Int f () = 1 This f isn't very useful; it's basically the same as "1". But consider this type: datatype stream = Stream of (int * (unit -> stream)) stream1 () = Stream(1, stream1) stream_take :: int*stream -> int list stream_take(0,_) = Nil stream_take(n,Stream(i,f)) = Cons(i, stream_take(n-1, f())) Now there is no way to pass a different value like we did in weird_take; there's only (). The difference is that the state gets embedded in the closure for the thunk: stream_ints :: int -> (unit -> stream) stream_ints = fun n => fun () => Stream(n, stream_ints(n+1)) What you are doing here is encoding laziness; the Haskell version of this type: > data Stream = Stream !Int Stream -- !Int means the Int value is strict > stream1 = Stream 1 stream1 > stream_ints n = Stream n (stream_ints(n+1)) > stream_take :: Int -> Stream -> [Int] > stream_take 0 _ = [] > stream_take n (Stream x xs) = x : stream_take (n-1) xs No extra (\() -> ...) thunk is required, due to laziness :) -- ryan On Tue, May 19, 2009 at 4:25 PM, michael rice <nowgate(a)yahoo.com> wrote: > Hi Ryan, > > I'm afraid you've lost me. Maybe if you showed how this would be used in ML > I would get the picture. > > Michael > > --- On Tue, 5/19/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > > From: Ryan Ingram <ryani.spam(a)gmail.com> > Subject: Re: [Haskell-cafe] showing a user defined type > To: "michael rice" <nowgate(a)yahoo.com> > Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, > haskell-cafe(a)haskell.org > Date: Tuesday, May 19, 2009, 2:40 PM > > On Tue, May 19, 2009 at 7:07 AM, michael rice <nowgate(a)yahoo.com> wrote: >> A little further along in "The Little MLer" the ints function is replaced >> by >> other functions like primes and fibs, which also return Links: >> >> fun primes(n) >> = if is_prime(n+1) >> then Link(n+1,primes) >> else primes(n+1) >> >> fun fibs(n)(m) >> = Link(n+m,fibs(m)) >> >> which are passed to chain_item: >> >> fun chain_item(n,Link(i,f)) >> = if eq_int(n,1) >> then i >> else chain_item(n-1,f(i)) >> >> which can be called to request the nth (12th) prime number beginning at 1. >> >> - chain_item(12,primes(1)); >> GC #0.0.0.1.3.61: (1 ms) >> val it = 37 : int >> - >> >> So I guess the answer to your question about whether the function is ever >> called with a different value may be, yes. > > Actually, it's not calling it with another value; notice that > chain_item calls f(i), with i coming directly from the chain. > Consider this alternate definition: > (I'm not sure the syntax is exactly right, but you get the idea) > > datatype chain = > Link of (int * ( unit -> chain )) > > fun intsFrom(n) = fun unit => (n, intsFrom (n+1)) > fun ints(n) = intsFrom n () > > Now you *can't* call the function embedded in the link with another value. > > fun chain_item(n,Link(i,f)) > = if eq_int(n,1) > then i > else chain_item(n-1,f unit) > > And this type for "chain" is almost the same as [Int] in Haskell, due > to laziness. > > -- ryan > >

2 1

Free theorems for dependent types?
by Eugene Kirpichov 21 May '09

21 May '09

Hello, Is there any research on applying free theorems / parametricity to type systems more complex than System F; namely, Fomega, or calculus of constructions and alike? This seems very promising to me for the following reason: Take the free theorem for 'sort::(a->a->Bool)->[a]->[a]'. The theorem could possibly be a lot more powerful if there were a way to encode in the type of 'sort' that it accepts a reflexive transitive antisymmetric predicate, but the only way to express that is with dependent types. Looks like the only thing one needs to add to System F is the relational translation rule for a dependent product; but I haven't tried doing it myself. -- Eugene Kirpichov Web IR developer, market.yandex.ru

7 11

Problem with haddock importing definition
by Maurício 20 May '09

20 May '09

Hi, I have a situation like this: module A imports R (a newtype declaration) from module B, and lists it in its (module A) export list. Documentation for R is included by haddock in documentation for module A, as I want. However, if my package exposes only module A, documentation for R desapears. So: if my .cabal file lists A and B in 'exposed-modules', documentation for R is included in A documentation. If I remove B from 'exposed-modules', R documentation in A desapears. Do you know what should I do? Thanks, Maurício

3 5

HaL4: Haskell-Treffen in Halle/Saale, 12. Juni 2009 - Programm und Anmeldung
by unknown＠example.com 20 May '09

20 May '09

Kindly excuse the German noise, please ... Liebe Haskell-Freunde! Das Programm fuer unser Haskell-Treffen steht jetzt so gut wie fest und man kann sich online anmelden. --------------------------------------------- HaL4 : Haskell - Tutorial + Workshop + Party am Freitag, dem 12. Juni 2009, in Halle/Saale --------------------------------------------- Das traditionsreiche HaL-Treffen bietet eine gute Mischung von Haskell-bezogenen Themen aus Forschung, Anwendung und Lehre mit vielen Möglichkeiten zu Diskussion und Unterhaltung bei der anschließenden Party. Der Workshop wird in diesem Jahr ergänzt durch Tutorien für Haskell-Ein- und Umsteiger. Diesmal findet das Treffen in Halle/Saale im Institut für Informatik der Martin-Luther-Universität Halle-Wittenberg statt. Wir bieten: 10 Uhr: Entwurfsmuster vom Kopf auf die Fuesse gestellt: data, fold und laziness statt Kompositum, Visitor, Iterator. Johannes Waldmann, HTWK Leipzig. 11 Uhr: CAL/openquark: (openquark.org) Haskell + Java => CAL, eine praktische Einfuehrung (Eclipse als CAL-IDE, Excel lesen, typsicheres SQL = LINQ fuer Java?) Alf Richter, iba Consulting, Leipzig 12 Uhr: Wie man das Semikolon ueberlaedt: Code-Strukturierung und -Wiederverwendung durch Monaden 15 Uhr: Hayoo! Haskell API Search Timo Huebel, FH Wedel 16 Uhr: Haskell als reine Spezifikationssprache Baltasar Trancon y Widemann, Universit Bayreuth 17 Uhr: Funktional-logische Programmierung mit Curry Jan Christiansen, Universitaet Kiel 19 - 22 Uhr: Grillparty Wir freuen uns auf rege Teilnahme sowie spannende Vorträge mit heißen Diskussionen und bitten um Anmeldung bis zum 31. Mai. Weitere Informationen auf http://www.iba-cg.de/hal4.html Beste Gruesse Henning Thielemann

1 0

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?
by spoon＠killersmurf.com 20 May '09

20 May '09

While just writing 33 instead of length [1..33] saves an awful lot of bother, the function you'd probably want in similar circumstances is `fromIntegral` See the Prelude. Also, you can use Data.ByteString.head instead of unpack and then Data.List.head rollDice :: Word8 -> IO Word8 rollDice n = do bracket (openFile "/dev/random" ReadMode) hClose (\hd -> do v <- fmap B.head $ B.hGet hd 1 return $ (v `mod` n) + 1)

1 0

Expression parsing problem
by leledumbo 20 May '09

20 May '09

I'm writing a paper as a replacement for writing exam and decided to write a simple compiler (got a little experience with it). However, I got trouble in parsing expression. The grammar: expression = "get" | [ "+" | "-" ] term { ( "+" | "-" ) term } term = factor { ( "*" | "/" ) factor } factor = IDENTIFIER | VALUE | "(" expression ")" I can't make term parse, for instance "1 * 2 / 3" (the number is not important, identifier is also accepted). It stops after parsing 2, i.e. only the first multiplication is parsed. Interchanging * and / gives the same result, only differs in operation. Whichever got encountered first will be parsed. The same problem also arises from expression, where it can't parse "1 + 2 - 3". Both problems are identical, but I can't figure out what's wrong (don't count the optional +/- before term in expression, I haven't done it yet). Sorry, but I'm lack of knowledge about Monad. I know it can be done better with it, but I need to learn a lot about it, while I don't have enough time (only 2 weeks). Below are necessary definitions for the parser (some taken from the scanner). For testing purpose, please try: expression [("1",Value),("+",Plus),("2",Value),("-",Minus),("3",Value),("EOF",EOF)] term [("1",Value),("*",Times),("2",Value),("/",Slash),("3",Value),("EOF",EOF)] expression [("1",Value),("-",Minus),("2",Value),("+",Plus),("3",Value),("EOF",EOF)] term [("1",Value),("/",Slash),("2",Value),("*",Times),("3",Value),("EOF",EOF)] > data Token = Identifier | OpenBlock | CloseBlock | SemiColon | Slash | > Equals | OpenBrace | CloseBrace | Minus | Times | > Plus | Nil | Value | Var | Const | > Put | Get | Comma | EOF > deriving (Show,Eq) > type Symbol = (String,Token) > type ASL = [Symbol] > type ParseFunc = ASL -> (ASL,[String]) > expression :: ParseFunc > expression (h:s) > | snd h == Get = (s,["IN"]) > | op `elem` [Plus,Minus] = (s2,r1 ++ r2 ++ [operation op]) > | otherwise = (s1,r1) > where (s1,r1) = term (h:s) > (s2,r2) = term $ tail s1 > op = if s1 /= [] then snd $ head s1 else Nil > expression s = (s,[]) > term :: ParseFunc > term s = if op `elem` [Times,Slash] > then (s2,r1 ++ r2 ++ [operation op]) > else (s1,r1) > where (s1,r1) = factor s > (s2,r2) = factor $ tail s1 > op = if s1 /= [] then snd $ head s1 else Nil > factor :: ParseFunc > factor ((id,Identifier):s) = (s,["LOAD " ++ id]) > factor ((val,Value):s) = (s,["PUSH " ++ val]) > factor (("(",OpenBrace):s) = if head s1 == (")",CloseBrace) > then (tail s1,r1) > else error $ "\")\" expected, got" ++ (show $ fst $ head s1) > where (s1,r1) = expression s > factor s = (s,[]) -- View this message in context: http://www.nabble.com/Expression-parsing-problem-tp23610457p23610457.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 8

Re: [Haskell-cafe] showing a user defined type
by michael rice 20 May '09

20 May '09

Hi Ryan, I'm afraid you've lost me. Maybe if you showed how this would be used in ML I would get the picture. Michael --- On Tue, 5/19/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "michael rice" <nowgate(a)yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, haskell-cafe(a)haskell.org Date: Tuesday, May 19, 2009, 2:40 PM On Tue, May 19, 2009 at 7:07 AM, michael rice <nowgate(a)yahoo.com> wrote: > A little further along in "The Little MLer" the ints function is replaced by > other functions like primes and fibs, which also return Links: > > fun primes(n) > = if is_prime(n+1) > then Link(n+1,primes) > else primes(n+1) > > fun fibs(n)(m) > = Link(n+m,fibs(m)) > > which are passed to chain_item: > > fun chain_item(n,Link(i,f)) > = if eq_int(n,1) > then i > else chain_item(n-1,f(i)) > > which can be called to request the nth (12th) prime number beginning at 1. > > - chain_item(12,primes(1)); > GC #0.0.0.1.3.61: (1 ms) > val it = 37 : int > - > > So I guess the answer to your question about whether the function is ever > called with a different value may be, yes. Actually, it's not calling it with another value; notice that chain_item calls f(i), with i coming directly from the chain. Consider this alternate definition: (I'm not sure the syntax is exactly right, but you get the idea) datatype chain = Link of (int * ( unit -> chain )) fun intsFrom(n) = fun unit => (n, intsFrom (n+1)) fun ints(n) = intsFrom n () Now you *can't* call the function embedded in the link with another value. fun chain_item(n,Link(i,f)) = if eq_int(n,1) then i else chain_item(n-1,f unit) And this type for "chain" is almost the same as [Int] in Haskell, due to laziness. -- ryan

2 1

Performance Problem with Typeable
by Michael D. Adams 20 May '09

20 May '09

I'm not sure where this should be reported, but I think I've found a significant asymptotic performance problem with Data.Typeable. In the attached code, sum2 runs much slower than either sum1 or sum3. It should be linear but it seems to slow down quadratically (i.e. doubling "len" quadruples the time for sum2). Here is an example run: $ ghc --make -O3 CastSpeed.hs $ ./CastSpeed 20000 gsum1 Result: 200010000 Time(sec): 7.999e-3 Result: 200010000 Time(sec): 0.0 Result: 200010000 Time(sec): 1.0e-3 gsum2 Result: 200010000 Time(sec): 1.483774 Result: 200010000 Time(sec): 1.477776 Result: 200010000 Time(sec): 1.523768 gsum3 Result: 200010000 Time(sec): 5.999e-3 Result: 200010000 Time(sec): 0.0 Result: 200010000 Time(sec): 0.0 The only difference between sum1 and sum2 is that sum2 wraps a singleton list around each element (i.e. the cast is to [Int] instead of Int). The only difference between sum2 and sum3 is that sum3 uses an unchecked cast (unsafeCoerce) instead of a checked cast. This problem seems to crop up only for those types which are made up of a type constructor applied to an argument (e.g. "[]" applied to "Int"). Because of sum3 runs fast, I suspect that something is going wrong with the "typeOf" call in a checked cast, and because sum1 runs fast I suspect that what is going wrong is the call to appKey that is called from mkAppTy that is called from typeOfDefault that is called from the Typeable instance for [Int] (i.e. instance (Typeable1 s, Typeable a) => Typeable (s a)). This is a bit of speculation and I don't have hard evidence for that being the source of the problems, but tests that I have run (not listed here) are strongly suggestive of appKey being the culprit. Michael D. Adams mdmkolbe(a)gmail.com

2 2

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?
by Lee Duhem 20 May '09

20 May '09

2009/5/20 Bernie Pope <florbitous(a)gmail.com>: > Oh right. I didn't see your proposal (did it get sent to the list?). Yes, I just push the Replay button, not the > Sorry for the confusion. It's my fault, sorry. lee

1 0

How i use GHC.Word.Word8 wit Int ?
by z_axis＠163.com 20 May '09

20 May '09

Hi, friends rollDice :: Word8 -> IO Word8 rollDice n = do bracket (openFile "/dev/random" ReadMode) (hClose) (\hd -> do v <- fmap B.unpack (B.hGet hd 1) let v1 = Data.List.head v return $ (v1 `mod` n) + 1) ..... blueIdx <- rollDice $ length [1..33] Couldn't match expected type `Word8' against inferred type `Int' In the second argument of `($)', namely `length yesBlue I know "length [1..33]" is Int not Word8, but Word8 is enough here. Sincerely!

4 3

How to use Data.ByteString ?
by z_axis 20 May '09

20 May '09

Hi, friends the following function works well rollDice n = getStdRandom (randomR (1,n)) :: IO Int now i want to use /dev/random to produce better random number, but it doesnot work rollDice_t n = do hd <- openFile "/dev/random" ReadMode v <- B.hGet hd 1 return (v `mod` n) + 1 No instance for (Integral B.ByteString) arising from a use of `mod' at Money.hs:15:12-20 Possible fix: add an instance declaration for (Integral B.ByteString) In the first argument of `return', namely `(v `mod` n)' In the first argument of `(+)', namely `return (v `mod` n)' In the expression: return (v `mod` n) + 1 then how to use the ByteString properly ? Sincerely!

5 6

fast Eucl. dist. - Haskell vs C
by Patrick Perry 20 May '09

20 May '09

Hi Kenneth, I wrote a benchmark similar to yours using the haskell blas library I wrote (latest version is on github at http://github.com/patperry/blas/tree/master , an older version is on hackage). The pure Haskell implementation is not very good, and the problem seems to be repeated boxing/unboxing of doubles. It may be possible to avoid this by writing a custom "fold" function for Vectors, but I haven't tried it. Using a vectorized subtraction function along with the BLAS1 "dnrm2" function, I was able to get performance about 2.8-5.4x worse than C. This isn't great, but it's not terrible, either. I didn't have the performance problems you ran in to using the FFI. My benchmark includes: distVectors1: a native implementation using foldl' and zipWith distVectors2: a vectorize implementation, defined as @distVectors2 x y = norm2 (x-y)@ distVectors3: a custom loop in haskell distVectors4: an FFI call to C All 4 functions use the "Vector" type, provided by the "blas" package. I compiled with "-O -fexcess-preceision" and ran timings for vectors of size 10, 100, and 1000. Here are the results: Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 10 n: 10 * distVectors1: ..................... 1.366ns per iteration / 732029.06 per second. * distVectors2: ..................... 1.286ns per iteration / 777734.02 per second. * distVectors3: ...................... 0.950ns per iteration / 1052847.93 per second. * distVectors4: ....................... 0.452ns per iteration / 2213752.56 per second. Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 100 n: 100 * distVectors1: .................. 12.496ns per iteration / 80025.79 per second. * distVectors2: .................... 2.149ns per iteration / 465311.61 per second. * distVectors3: .................. 8.728ns per iteration / 114572.53 per second. * distVectors4: ...................... 0.597ns per iteration / 1675765.65 per second. Macintosh-62:~/Code/blas/examples (euclidean)$ ./Euclidean 1000 n: 1000 * distVectors1: .............. 125.920ns per iteration / 7941.52 per second. * distVectors2: .................. 10.677ns per iteration / 93661.99 per second. * distVectors3: ............... 85.533ns per iteration / 11691.42 per second. * distVectors4: .................... 1.962ns per iteration / 509668.17 per second. The "distVectors2" function is computing the norm in a more numerically-stable way. It is also allocating a temporary array to store x-y. I haven't looked over your benchmarking code too thoroughly, but parts of it seem suspect to me. Namely, you are using "mapM" instead of "mapM_". Also, it seems like you are including GC times in your benchmarks. Attached is my code. You will need the latest "blas" from github to compile it. You also might want to look into hmatrix. I have very little time for haskell code right now (I'm trying to finish my Ph.D. in the next month). This summer I plan to work more on this stuff, and I'll probably make a release in July. Patrick

1 0

ANN: atom 0.0.4
by Tom Hawkins 20 May '09

20 May '09

This new version of atom adds an array datatype (A a), which has helped us shrink and speed up the embedded code in our application. Enjoy! http://hackage.haskell.org/cgi-bin/hackage-scripts/package/atom -Tom

1 0

Gtk2Hs + Sourceview on Windows
by mwinter＠brocku.ca 20 May '09

20 May '09

Hi, I have ghc 6.10.1 and gtk2hs 0.10.0 installed on my windows vista computer. Both were installed using the installer on the webpages. I am able to use gtk, glade etc but not sourceview or cairo. If I compile the examples in the gtk2hs example folder, I get "not in scope" error messages for functions from those library components. In a forum I found that those have to be enabled using ./configure --enable-sourceview (similar for cairo). But my windows installation does not seem to have a script configure or a similar program. What am I supposed to do? Thanks, Michael ---------------------------------------------------------------------------------------------- Michael Winter Brock University Associate Professor 500 Glenridge Avenue Department of Computer Science St. Catharine, ON, L2S 3 A1 Phone: +1 905 688 5550 ext 3355 Fax: +1 905 688 3255 ---------------------------------------------------------------------------------------------

1 0

Question about IO, interact functions,
by David Leimbach 20 May '09

20 May '09

main = interact (unlines . lines) This *appears* to somewhat reliably get me functionality that looks like take a line of input, and print it out. Is this behavior something I can rely on working? I like the idea that lines can pull lines lazily from "getContents" which lazily consume the input. But I'm concerned that relying on a pure function like "unlines . lines" to sequence IO is a bit too implicit in nature. I really like the idea of doing things through functions like Interact in that they appear to allow me to keep most of my code pure, but if I can't get the IO sequencing I want to be guaranteed to work, I suppose I'll have to dive back into "imperative IO" land that I get from the IO Monad. Should I feel guilty for doing so? :-) Dave

3 2

Re: [Haskell-cafe] showing a user defined type
by michael rice 20 May '09

20 May '09

Thanks. I had put together something similar to your first suggestion but tried to use PutStrLn(Show...). I'd also thought of your second suggestion about a dummy show for functions. A little further along in "The Little MLer" the ints function is replaced by other functions like primes and fibs, which also return Links: fun primes(n) = if is_prime(n+1) then Link(n+1,primes) else primes(n+1) fun fibs(n)(m) = Link(n+m,fibs(m)) which are passed to chain_item: fun chain_item(n,Link(i,f)) = if eq_int(n,1) then i else chain_item(n-1,f(i)) which can be called to request the nth (12th) prime number beginning at 1. - chain_item(12,primes(1)); GC #0.0.0.1.3.61: (1 ms) val it = 37 : int - So I guess the answer to your question about whether the function is ever called with a different value may be, yes. Michael --- On Mon, 5/18/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu> Cc: "michael rice" <nowgate(a)yahoo.com>, haskell-cafe(a)haskell.org Date: Monday, May 18, 2009, 10:02 PM Unfortunately, you can't derive Show on Chain as defined, because it contains a function: > data Chain = Link Int (Int -> Chain) You can write this: > instance Show Chain where > show (Link n _) = "Link " ++ show n ++ " <fn>" Or you can make a dummy "Show" instance for functions: > instance Show (a -> b) where show _ = "<fn>" > data Chain = Link Int (Int -> Chain) deriving Show One question: Do you expect to ever call the function with a different value? For example: otherChain :: Chain otherChain = case (ints 0) of Link _ f -> f 100 If not, you can replace Chain entirely by [Int], due to laziness, something that's not possible in ML. (Although you can get the same result in ML by using (int * (() -> chain)) instead. -- ryan On Mon, May 18, 2009 at 6:36 PM, Brandon S. Allbery KF8NH <allbery(a)ece.cmu.edu> wrote: > On May 18, 2009, at 21:19 , michael rice wrote: > > *Main> :t ints 0 > ints 0 :: Chain > *Main> ints 0 > > <interactive>:1:0: > No instance for (Show Chain) > > In general, you want to append > deriving Show > to your types. You may also want to be able to input them in ghci, so > instead say > deriving (Show, Read) > -- > brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery(a)kf8nh.com > system administrator [openafs,heimdal,too many hats] allbery(a)ece.cmu.edu > electrical and computer engineering, carnegie mellon university KF8NH > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

2 1

Re: [Haskell-cafe] showing a user defined type
by michael rice 19 May '09

19 May '09

Cool! Is there *anything* Haskell *can't* do? Michael --- On Mon, 5/18/09, David Menendez <dave(a)zednenem.com> wrote: From: David Menendez <dave(a)zednenem.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "Ryan Ingram" <ryani.spam(a)gmail.com> Cc: haskell-cafe(a)haskell.org Date: Monday, May 18, 2009, 10:26 PM On Mon, May 18, 2009 at 10:02 PM, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > Unfortunately, you can't derive Show on Chain as defined, because it > contains a function: Sure you can. I just tried the following, and it compiled without complaints. > import Text.Show.Functions > > data Chain = Link Int (Int -> Chain) deriving (Show) The usual warnings about orphan instances apply, but the purpose of the Text.Show.Functions module is to provide a standard Show instance for functions so that libraries (e.g., QuickCheck) don't declare conflicting instances. -- Dave Menendez <dave(a)zednenem.com> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

RE: [Haskell-cafe] Request for feedback: HaskellDB + HList
by Brian Bloniarz 19 May '09

19 May '09

Hi Justin, I updated my changes to apply against that repo, thanks for the pointer. Cool to see new changes to haskelldb, especially all the new unit tests! You can find my updated repo at: http://patch-tag.com/r/haskelldb-hlist Re-reading your email now, I see you asked for a patch, but seeing patch-tag for the first time I got excited and uploaded a whole new repo, whoops. Anyway, I had to do some minor surgery to update to the new version -- everything compiles, but I haven't tested much beyond that yet. Let me know if you have any questions. Thanks, -Brian > I like the direction you are going. I looked into using HList a year > or so ago and I wasn't quite up to it. The latest (unreleased) > version of HaskellDB is on patch-tag at > http://patch-tag.com/r/haskelldb/snapshot/current/content/pretty. > Would you mind creating a patch file against that for easier review? I > won't commit it until you say its ready but I'd like to see what > changes you have made. > > No announcement has been made but I took over maintainership from > Bjorn a few months ago. I hope to get a 1.0 release of HaskellDB out > this summer, and having something new like this in it would be pretty > sweet. > > On Sat, May 16, 2009 at 3:08 PM, Brian Bloniarz <phunge0(a)hotmail.com> wrote: > > Hi, > > > > It's come time to share something that I've been playing around with > > recently: > > a branch of HaskellDB which replaces the home-grown Record code with HList > > records. It's definitely not ready for primetime, but I thought it'd be a > > good > > time to post the code and solicit some feedback from the community. > > > > HaskellDB the concept is very promising, but IMHO the code still falls short > > of that promise. Hopefully this is a small step in the right direction -- > > the > > advantages of using HList: > > * Shared implementation of extensible records > > * Additional features from HList > > * Better error messages for record misuse > > * "Lacks" predicates > > * Simpler code > > > > As an example of how this can be better, a DB insert looks like so: > >> insert db table $ constantRecord $ > >> film .=. "Munchie" .*. > >> director .=. Just "Jim Wynorski" .*. > >> emptyRecord > > The columns need not appear in the same order as in the database. If you > > forget > > a column, you'll get "error: No instance for (Fail (FieldNotFound (Proxy > > Director)))" > > rather than an opaque error. Using the new "insertOpt" function, Maybe > > columns > > will default to Nothing rather than needing to be specified. > > > > The details: > > > > I haven't updated everything, but there's enough to run test/TestCases.hs > > under Postgresql. TestCases is probably the best place to look for examples > > of > > the new syntax for now. > > > > HList had name conflicts with HaskellDB's SQL expression language > > ((.*.), (.++.), etc.) My temporary band-aid is to move the expression > > functions > > to Database.HaskellDB.SqlExpr, and require people to import qualified. > > > > The Attr type is gone, columns labels are untyped now. I also replaced a > > few instances of primitive type-level recursion with HMap/HMapOut. This > > makes > > the code simpler, and the type signatures more complex -- type families > > would > > help a lot here, I think. > > > > Feedback welcome! You can find my darcs tree at: > > > > http://mysite.verizon.net/vzewxzuh/sitebuildercontent/sitebuilderfiles/hask… > > It also requires minor changes to HList, available at: > > > > http://mysite.verizon.net/vzewxzuh/sitebuildercontent/sitebuilderfiles/hlis… > > I'll talk to the HList people about getting those merged. > > > > Thanks! > > > > Brian Bloniarz > > > > > > ________________________________ > > Hotmail® has a new way to see what's up with your friends. Check it out. > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > _________________________________________________________________ Hotmail® has ever-growing storage! Don’t worry about storage limits. http://windowslive.com/Tutorial/Hotmail/Storage?ocid=TXT_TAGLM_WL_HM_Tutori…

1 0

Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
by Daniel Schüssler 19 May '09

19 May '09

Hello! On Monday 18 May 2009 14:37:51 Kenneth Hoste wrote: > I'm mostly interested in the range 10D to 100D is the dimension known at compile-time? Then you could consider Template Haskell. I wrote up some code for generating the vector types and vector subtraction/inner product below, HTH. One problem is that I'm using a typeclass and apparently you can't make {-# SPECIALISE #-} pragmas with TH, so let's hope it is automatically specialised by GHC. Greetings, Daniel TH.hs ------------------ {-# LANGUAGE TemplateHaskell #-} {-# OPTIONS -fglasgow-exts #-} module TH where import Language.Haskell.TH import Control.Monad -- Non-TH stuff class InnerProductSpace v r | v -> r where innerProduct :: v -> v -> r class AbGroup v where minus :: v -> v -> v euclidean x y = case minus x y of z -> sqrt $! innerProduct z z -- TH noContext :: Q Cxt noContext = return [] strict :: Q Type -> StrictTypeQ strict = liftM ((,) IsStrict) makeVectors :: Int -- ^ Dimension -> Q Type -- ^ Component type, assumed to be a 'Num' -> String -- ^ Name for the generated type -> Q [Dec] makeVectors n ctyp name0 = do -- let's assume ctyp = Double, name = Vector for the comments -- generate names for the variables we will need xs <- replicateM n (newName "x") ys <- replicateM n (newName "y") let name = mkName name0 -- shorthands for arithmetic expressions; the first takes expressions, -- the others take variable names sumE e1 e2 = infixE (Just e1) [|(+)|] (Just e2) varDiffE e1 e2 = infixE (Just (varE e1)) [|(-)|] (Just (varE e2)) varProdE e1 e2 = infixE (Just (varE e1)) [|(*)|] (Just (varE e2)) conPat vars = conP name (fmap varP vars) -- > data Vector = Vector !Double ... !Double theDataD = dataD noContext name [] -- no context, no params [normalC name (replicate n (strict ctyp))] [''Eq,''Ord,''Show] -- 'deriving' clause innerProdD = -- > instance InnerProductSpace Vector Double where ... instanceD noContext ( conT ''InnerProductSpace `appT` conT name `appT` ctyp) -- > innerProduct = ... [valD (varP 'innerProduct) (normalB -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) -> (lamE [conPat xs, conPat ys] -- x1*y1 + .... + xn*yn + 0 (foldl sumE [|0|] $ zipWith varProdE xs ys) )) [] -- no 'where' clause ] abGroupD = instanceD noContext ( conT ''AbGroup `appT` conT name) -- > minus = ... [valD (varP 'minus) (normalB -- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) -> (lamE [conPat xs, conPat ys] -- Vector (x1-y1) ... (xn-yn) (foldl appE (conE name) $ zipWith varDiffE xs ys) )) [] -- no 'where' clause ] sequence [theDataD,innerProdD,abGroupD] Main.hs ------------------ {-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE MultiParamTypeClasses #-} module Main where import TH $(makeVectors 3 [t|Double|] "Vec3") main = print $ euclidean (Vec3 1 1 1) (Vec3 0 0 0)

2 2

fast Eucl. dist. - Haskell vs C
by Kenneth Hoste 19 May '09

19 May '09

Hello, For a while now, I've been trying to come up with a fast Haskell-only function which implements Euclidean distance in n-dimensional space. So far, I've been disappointed by the performance of my best effort in Haskell, compared to C. I'm hoping some of the Haskell experts and/or performance gurus on this list can help me out on resolving this, and also maybe shed some light on some strange (imho) things I've run into. My current best try uses the uvector package, has two 'vectors' of type (UArr Double) as input, and relies on the sumU and zipWithU functions which use streaming to compute the result: dist_fast :: UArr Double -> UArr Double -> Double dist_fast p1 p2 = sumDs `seq` sqrt sumDs where sumDs = sumU ds ds = zipWithU euclidean p1 p2 euclidean x y = d*d where d = x-y I've been benchmarking this function against various alternatives using the MicroBench [1] package, which allows to get accurate timings of single function calls. I've also mimicked the MicroBench approach in pure C, to get comparable timings for a C-only implementation. The C-only function is quite straightforward: double dist(int dim, double* p1, double* p2){ int i; double d = 0.0; for(i=0; i < dim; i++){ d += (p1[i] - p2[i])*(p1[i] - p2[i]); } return sqrt(d); } (Note that the optimizer takes care of the p1-p2 operation appearing twice in the code). All code is attached if you'd like to play around with it. All numbers reported below are using GHC 6.10.2 and gcc 4.3.3 on Linux/x86. The compilation details can be found in the Makefile attached, but in short, I'm using -O2 -fexcess-precision or -O2 -fexcess-precision -fvia-C -optc-O3 with GHC, and -O3 with gcc. Now the bad news: for small dimensions, e.g. 2D/3D-space, the dist_fast function is 70-240x slower than a pure C implementation, depending on the architecture. For example, in 2D-space on an Intel Pentium 4 (3.0GHz, 1M L2 cache), a single call to dist_fast takes about 1.75 microseconds (or 0.00000175s), while a call to dist_c (C implementation of Eucl. dist), takes about 0.025 microseconds (70x slowdown). On a Core 2 2.5GHz with 6MB L2 this maps to 1.9 and 0.008 microseconds, resp. (i.e. 240x slower), while on a Core i7 2.66GHz with 8MB L2 the numbers are 1.53 and 0.011 microseconds (i.e. 140x slower). For larger dimensions, the gap becomes less big, but is still worrying: 10D: 40-110x; 100D: 10-17x; >1kD: 2.5x-6x. I'm mostly interested in the range 10D to 100D, so seeing that Haskell is over 10x and up to 100x slower than C is kind of making me cry. I've tried some things to improve on this without much luck, on the contrary: *) Marking dist_fast for inlining makes things worse; in general the inlined version is 2x slower for low dimensionality, and even 5x slower for larger dimensionality. This was somewhat surprising to me... *) In a moment of weakness, I used the Foreign Function Interface to call the dist_c C-only implementation from Haskell. Unfortunately, there seems to be a lot of overhead in calling dist_c from Haskell. Most of the performance gain from using C melts away, and sometimes the performance of the FFI'd dist_c is 15-30% worse than the native dist_fast version (especially at low dimensionality). Only for the largest dimensionalities (10k-100kD), the FFI'd version reaches the performance of the native C approach. But, since I'm mostly interested in the 10-100D range, this is of little use to me. One thing I noticed is that compiling through C using -fvia-C -optc-O3 might be a bad idea, depending on your system. On an Intel Pentium 4 system, -fvia-C -optc-O3 was giving me a speedup of up 70% (large dim.), while on Core 2 and Core i7 it resulted in a slowdown of 15-20% ! I was using roughly equal versions of GCC with this, i.e. a self-bootstrapped GCC 4.3.x. So, my question to the list if simple: how can I get better performance out of a Haskell-only approach? Any comments/suggestions are highly appreciated. I'd prefer a Haskell-only approach, but my main concern is speed. The Euclidean distance function will be used quite heavily in various tools. I currently have a C-version of some of the tools, but the amount of code that is needed for those tools is becoming ridiculously big. I believe using Haskell will allow me to come up with a more easy to maintain code base. However, I don't want to pay a huge price for this in terms of performance. greetings, Kenneth [1] MicroBench: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/microbench -- Kenneth Hoste Paris research group - ELIS - Ghent University, Belgium email: kenneth.hoste(a)elis.ugent.be website: http://www.elis.ugent.be/~kehoste blog: http://boegel.kejo.be

5 14

Re: Haskell-Cafe Digest, Vol 69, Issue 38
by Tom Lokhorst 19 May '09

19 May '09

These QuickCheck properties don't really test your sort function. The `a' type variable will be instantiated to (). So you will test with lists of units, like so: ghci> quickCheck (\xs -> isSorted (reverse xs)) OK, passed 100 tests. This can be simply solved by added a more specific type signature: isSorted :: [Int] -> Bool Surly, if the sort function works for Ints, it'll work for any Ord a. - Tom > ---------- Forwarded message ---------- > From: Ryan Ingram <ryani.spam(a)gmail.com> > To: Eugene Kirpichov <ekirpichov(a)gmail.com> > Date: Mon, 18 May 2009 13:57:04 -0700 > Subject: Re: [Haskell-cafe] Haskell in 3 Slides > On Mon, May 18, 2009 at 11:33 AM, Eugene Kirpichov <ekirpichov(a)gmail.com> wrote: >> The main bullet point is missing: Correctness. >> >> How could we have forgotten quickcheck? >> >>> quickCheck (\xs -> sort (sort xs) == sort xs) >> OK, 100 tests passed. > > I like this, but given that you have a whole slide, I might write this: > > isSorted :: Ord a => [a] -> Bool > isSorted [] = True > isSorted [x] = True > isSorted (x:y:rest) = x <= y && isSorted (y:rest) > >> quickCheck (\xs -> isSorted (sort xs)) > OK, 100 tests passed. > > Or, if you want to lead into a talk about fusion and/or higher order functions: > > isSorted [] = True > isSorted (x:xs) = snd $ foldl' check (head x, True) xs where > check (prevElem, restSorted) thisElem = (thisElem, prevElem <= > thisElem && restSorted) > > -- ryan >

1 0

[ANN] Safe Lazy IO in Haskell
by Nicolas Pouillard 19 May '09

19 May '09

Hi folks, We have good news (nevertheless we hope) for all the lazy guys standing there. Since their birth, lazy IOs have been a great way to modularly leverage all the good things we have with *pure*, *lazy*, *Haskell* functions to the real world of files. We are happy to present the safe-lazy-io package [1] that does exactly this and is going to be explained and motivated in the rest of this post. === The context === Although these times were hard with the Lazy/IO technique, some people continue to defend them arguing that all discovered problems about it was not that harmful and that taking care was sufficient. Indeed some issues have been discovered about Lazy/IOs, some have been fixed in the underlying machinery, some have just been hidden and some others are still around. == An alternative == An alternative design has been proposed --and is still evolving--, it is called "Iteratee" [2] and has been designed by Oleg Kiselyov. This new design has tons of advantages over standard imperative IOs, and shares some of the goals of Lazy/IOs. Iteratee provides a way to do incremental processing in a high-level style. Indeed both processed data (via enumerators) and processing code (called iteratee) can be modularly composed. The handling of file-system resources is precise and safe. Catching errors can be done precisely and can be interleaved with the processing. In spite of all this, there is an important drawback: a lot of code has to be re-written and thought in another way. Processing becomes explicitly chunked which is not always needed and, even worse, exceptions handling also becomes very explicit. While this makes sense in a wide range of applications it makes things less natural than the general case of pure functions. We think that Iteratee have too be studied more, and we recommend them when you have incrementally react to IO errors. == Issues of Standard Lazy/IO == We think that we can save Lazy/IO cheaply, but before explaining the way we solve such and such issue, let's first expose Lazy/IO and its issues. One of the main Lazy/IO functions is 'readFile': it takes a file path opens it and returns the list of characters until the end of the file is reached. The characteristic of 'readFile' is that only the opening is done strictly, while the reading is performed lazily as much as the output list is processed. Cousins of 'readFile' are 'hGetContents' that takes a file handle and 'getContents' that reads on the standard input. This technique enables to process a file as if the file was completely stored in memory. Because it is read lazily one knows that only the required part of the file will be read. Even better, if the input is consumed to produce a small output or the output is emitted incrementally, then the processing can be done in constant memory space. Examples: -- Prints the number of words read on stdin > countWords = print . length . words =<< getContents -- Prints the length of the longest line > maxLineLen = print . maximum . map length . lines =<< getContents -- Prints in lower case the text read on stdin > lowerText = interact (map toLower) -- Alternatively > lowerText = putStr . map toLower =<< getContents All these examples are pretty idiomatic Haskell code and make a simple use of Lazy/IOs. Each of them runs in constant memory space even if they are declared as if the whole contents were available at once. By using stream fusion or 'ByteString''s one can get even faster code while keeping the code almost the same. Here we will stay with the default list of 'Char''s data type. However one goal of our approach is to be trivially adaptable to those data types. Using our library will be rougly a matter of namespace switch plus a running function: > lowerText = LI.run' (SIO.putStr . map toLower <$> LI.getContents) However we will introducing this library as one goes along. Here is another example where the Lazy/IO are still easy to use but no longer scales well. This program counts the lines of all the files given in arguments: > countLines = print . length . lines . concat =<< mapM readFile =<< getArgs Here the problem is the limitation of simultaneous opened files. Indeed, all the files are opened at the beginning therefore reaching the limit easily. It's time to recall when the files are closed. With standard Lazy/IOs the handle is closed when you reach the end of the file, and so when you've explored the whole list returned by 'readFile'. Note also that if you manually open the file and get a handle, then you can manually close the file, however if by misfortune you close the file and then still consume the lazy list you will get a truncated list, observing how much of the file has been read. This last point is due to the fact that 'readFile' considers the reading error as the end of the file. In particular one can fix this program, by simply counting the number of lines of each file separately and then compute the sum to get the final result. > countLines = print . sum =<< mapM (fmap (length . lines) . readFile) =<< getArgs However once again this program exhausts the handle resources. Trying to close the files will not save us either, one just risks getting truncated files. Indeed the list of intermediate results is produced eagerly but each intermediate result is lazy and then each file is opened but not immediately closed since the computation is delayed. Hopefully adding a bit of strictness cures the problem: > countLines = print . sum =<< mapM ((return' . length . lines =<<) . readFile) =<< getArgs > where return' x = x `seq` return x Until there, we have disclosed three problems: * while reading is lazy, opening is strict, which leads to a less natural processing of multiple files * the closing of files is hard to predict * the errors during reading are silently discarded The last one is a bit trickier and has recently been exposed by Oleg Kiselyov [3]. The problem appears when one gets twice the contents of the same stream---or some kind of inter-dependent streams. Because reading is implicitly driven by the consumer, the interleaving of reading may then depend on the reduction strategy employed. This is the case even if the consumer is a pure function. Basically in this example one can observe different values when using one of these functions: > f1 x y = x `seq` y `seq` x - y > f2 x y = y `seq` x `seq` x - y In this example one reads stdin twice and relies on the error handling to end one stream while keeping the other opened. Moreover there are other ways to achieve this like the use of unix fifo files, or using 'getChanContents' from the "Control.Concurrent.Chan" module. === Our solution === Here we will present another design, based on a very simple idea. Our goal is to provide IO processing in a style very similar to standard Lazy/IO with the following differences: - preservation of the determinism; - a simple control exceptions; - and a precise management of resources. Our solution is made of three key ingredients: a bit of strictness, some predefined schemas to interleave inputs, some scopes and abstract types to delimit lazy input operations from strict IO operations. == Dealing with a single input == Let's present the first ingredient alone through a first example: > mapHandleContents :: NFData sa => Handle -> (String -> sa) -> IO sa > mapHandleContents h f = do > s <- hGetContents h > return' (f s) `finally` hClose h > return' :: (Monad m, NFData sa) => sa -> m sa > return' x = rnf x `seq` return x It implements some combination of 'fmap' and 'hGetContents'. Actually some of our examples fit nicely in that model: > countWords = print =<< mapHandleContents stdin (length . words) > maxLineLen = print =<< mapHandleContents stdin (maximum . map length . lines) > lowerText = putStr =<< mapHandleContents stdin (map toLower) However while the two first examples work well in this setting, the third one tries to allocate the whole result in memory before printing it. Here the ingredient that is used is strictness: the purpose in forcing the result is to be sure that all the needed input is read, before the file is closed. So here we rely on 'NFData' instances to really perform deep forcing---this kind of assumption is a bit like 'Typeable' instances. In particular functions must not be an instance of 'NFData': indeed, we have no way to force lazy values that are stored in the closure of a function. The same remark applies to the 'IO' monad for at least three reasons: 'IO' if often represented by functions; lazy 'IORef''s could be used to hide one input for later use; exceptions with a lazy contents could also be used to make a lazy value escape. Let's now add some more strictness into the meal: the 'SIO' monad! == The 'SIO' monad == The 'SIO' monad is a thin layer over the 'IO' monad, populated only by strict 'IO' operations. In particular these operations are strict in the output, which means that once the output is produced then we know that the given arguments cannot be further evaluated/forced. Here is an example of strict IO using the 'SIO' monad: > import qualified System.IO.Strict as SIO > import System.IO.Strict (SIO) > countWords = SIO.run (SIO.print . length . words =<< SIO.getContents) Of course this function does not scale well since it reads the whole contents in memory before processing it. For now the strict-io [4] package contains wrappers for functions in "System.IO", and strict 'IORef''s. One can now introduce a function in lines of 'mapHandleContents': > withHandleContents :: NFData sa => Handle -> (String -> SIO sa) -> IO sa > withHandleContents h f = do > s <- hGetContents h > SIO.run (f s) `finally` hClose h One can then rewrite 'lowerText' as follow: > lowerText = withHandleContents stdin (SIO.putStr . map toLower) Until there one can deal quite nicely with single input, many outputs processing. Currently the only requirement is to delimit a scope where the resource will be used to return a strict value. Dealing with multiple inputs will lead us to our final design of lazy inputs. == Introducing 'LI', Lazy Inputs == We first introduce a type for these lazy inputs namely 'LI'. This type is abstract and we will progressively introduce functions to build, combine and run them. The 'LI' type is a pointed functor, but not necessarily a monad nor an applicative functor. Therefore one exports the 'pure' function as 'pureLI'. Building primitives allow to read files or handles: > LI.pureLI :: a -> LI a > LI.hGetContents :: Handle -> LI String > LI.getContents :: LI String > LI.readFile :: FilePath -> LI String > LI.getChanContents :: Chan a -> LI [a] Being a functor is important: it allows to wholly transform the underlying input lazily using standard functions about lists for instance: > length <$> LI.readFile "foo" > words <$> LI.readFile "foo" Extracting a final value of a lazy input ('LI' type) is a matter of using: > LI.run :: (NFData sa) => LI sa -> IO sa Or > LI.run' :: (NFData sa) => LI (SIO a) -> IO sa One can therefore re-write our examples using lazy inputs: > -- embedded printing > countWords = LI.run' (SIO.print . length . words <$> LI.getContents) > -- external printing > maxLineLen = print =<< LI.run (maximum . map length . lines <$> LI.getContents) > lowerText = LI.run' (SIO.putStr . map toLower <$> LI.getContents) == Combining inputs == Finally we come to managing multiple inputs. To get both laziness and precise resource management we will provide dedicated combinators. The first one is as simple as appending. > LI.append :: NFData sa => LI [sa] -> LI [sa] -> LI [sa] This one produces a single stream out that sequences the two given streams. It also sequences the usage of resources: the first resource is closed and then the second one is opened. Note that this combinator is still quite general since one can process each input beforehand: > -- one can drop parts of the inputs > (take 100 <$> i1) `LI.append` (drop 100 <$> i2) > -- one can tag each input to know where they come from > Left <$> i1 `LI.append` Right <$> i2 The second one is 'LI.zipWith' which opens the two resources and joins the items into a single stream. Again, since 'LI' is a functor one can join not only characters but also words, lines, chunks... A problem with zipping is that it stops on the shorter input (loosing a part of the other), hopefully one can prolongate them: > zipMaybesWith :: (NFData sa, NFData sb) -> (Maybe sa -> Maybe sb -> c) -> LI [sa] -> LI [sb] -> LI [c] > zipMaybesWith f xs ys = > map (uncurry f) . takeWhile someJust <$> zip (prolongate <$> xs) (prolongate <$> ys) > where someJust (Nothing, Nothing) = False > someJust _ = True > prolongate :: [a] -> [Maybe a] > prolongate zs = map Just zs ++ repeat Nothing The last one is 'LI.interleave': > LI.interleave :: (NFData sa) -> LI [sa] -> LI [sa] -> LI [sa] This function is currently left biased, moreover each resource is closed as soon as we reach its end. However since the inputs are mixed up together one generally prefers a tagged version trivially build upon this one: > interleaveEither :: (NFData sa, NFData sb) => LI [sa] -> LI [sb] -> LI [Either sa sb] > interleaveEither a b = interleave (map Left <$> a) (map Right <$> b) Here are some final programs that scale well with the number of files. > -- number of words in the given files > main = print =<< LI.run . fmap (length . words) . LI.concat . map LI.readFile =<< getArgs > -- almost the same thing but counts words independently in each file > main = print > =<< LI.run . fmap sum . LI.sequence . map (fmap (length . words) . LI.readFile) > =<< getArgs > -- prints to stdout swap-cased concatenation of all input files > main = LI.run' . (fmap (SIO.putStr . fmap swapCase) . LI.concat . map LI.readFile) =<< getArgs > where swapCase c | isUpper c = toLower c > | otherwise = toUpper c > -- sums character code points of inputs > main = print =<< LI.run . fmap (sum . map (toInteger . ord)) . LI.concat . map LI.readFile =<< getArgs Our solution is from now widely available as an Hackage package named "safe-lazy-io" [4]. We hope you will freely enjoy using Lazy/IO again! As usual, criticisms, comments, and help are expected! Finally, I would like to thank Benoit Montagu and Francois Pottier for helping me out to polish this work! [1]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-lazy-io [2]: http://okmij.org/ftp/Streams.html [3]: http://www.haskell.org/pipermail/haskell/2009-March/021064.html [4]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/strict-io -- Nicolas Pouillard

9 25

GUIs, FRP, (Delimited) Continuations and Zippers
by Günther Schmidt 19 May '09

19 May '09

Hi all, In my app, there is one part which has a rather complicated GUI logic, it involves n drop downs with n choices each. Whenever the current selection in one of the drop downs changes by user interaction, the other (n-1) drop downs need to be notified and their item list need to possible change too. Now I have managed to code all this and it actually behaves correctly. But I'm also using tons of IORefs and tons of bookkeeping code for it. While I'd not be ashamed to show any other part of my code to another Haskeller, this part of the code is the most clumsiest I've ever written. And I have no clue if that piece of code *can* be written in any other way, ie. without the tons of IORefs and bookkeeping. The GUI library is WXHaskell. In the last few days I read up on Conal Elliotts FRP stuff (reactive) but also on Olegs ZFS (Zippers, Delimited Continuations), the latter leaving me totally baffled. Could either of those approaches (FRP / Delimited Continuations) be a solution for implementing complex GUI code? Günther

2 1

GUIs, FRP, (Delimited) Continuations and Zippers
by oleg＠okmij.org 19 May '09

19 May '09

> Could either of those approaches (FRP / Delimited Continuations) be a > solution for implementing complex GUI code? I think the answer is generally yes; I have tried writing a user interface which has a form with several controls; a change in one control may affect all other controls on the form (or change the form). I have tried it for a particular GUI: the web page -- displayed in a browser interacting with a CGI script. The choice of CGI was deliberate because it is harder than FastCGI: it requires the ability to save the state of the interaction. The continuation must outlive its process. The point I was trying to make is that the GUI is programmed as if it were a uncursed console application: you send one question, get a reply, send another question, etc. With a GUI, questions are sent in parallel and answers are delivered in any order; yet the programmer can still think he deals with a regular console application; as if the interaction never happens and the program merely reads the data from a file. http://okmij.org/ftp/Computation/Continuations.html#shift-cgi It was done in OCaml though (because OCaml has native persistent delimited continuations).

1 0

Lawvere papers
by Vasili I. Galchin 19 May '09

19 May '09

Hello, I know that some Lawvere papers are available on TAC, but is there a list of all Lawvere papers online and where? Kind regards, Vasili

1 0

old Hugs libraries?
by Vasili I. Galchin 19 May '09

19 May '09

Hello, Do newSTArray, readSTArray, writeSTArray, etc. belong to an old deprecated Hugs library/module? If so, what is the Haskell 98 replacement? Thanks, Vasili

3 3

RE: [Haskell-cafe] Request for feedback: HaskellDB + HList
by Brian Bloniarz 19 May '09

19 May '09

_________________________________________________________________ Insert movie times and more without leaving Hotmail®. http://windowslive.com/Tutorial/Hotmail/QuickAdd?ocid=TXT_TAGLM_WL_HM_Tutor…

1 0

showing a user defined type
by michael rice 19 May '09

19 May '09

I've been playing around with "The Little MLer" (pg. 95, 96) to try to improve my understanding of types. I can ask ML: - ints(0); val it = Link (1,fn) : chain - and Haskell: *Main> :t ints 0 ints 0 :: Chain *Main> ints 0 <interactive>:1:0: No instance for (Show Chain) arising from a use of `print' at <interactive>:1:0-5 Possible fix: add an instance declaration for (Show Chain) In a stmt of a 'do' expression: print it *Main> I think I need to write a show function for type Chain but not sure how to proceed. Michael =============== ;;ML datatype chain = Link of (int * (int -> chain)) fun ints(n) = Link(n + 1, ints) ;;Haskell data Chain = Link Int (Int -> Chain) ints :: Int -> Chain ints n = Link (n+1) ints

4 3

showing a user defined type
by michael rice 19 May '09

19 May '09

I've been playing around with "The Little MLer" (pg. 95, 96) to try to improve my understanding of types. I can ask ML: - ints(0); val it = Link (1,fn) : chain - and Haskell: *Main> :t ints 0 ints 0 :: Chain *Main> ints 0 <interactive>:1:0: No instance for (Show Chain) arising from a use of `print' at <interactive>:1:0-5 Possible fix: add an instance declaration for (Show Chain) In a stmt of a 'do' expression: print it *Main> I think I need to write a show function for type Chain but not sure how to proceed. Michael =============== ;;ML datatype chain = Link of (int * (int -> chain)) fun ints(n) = Link(n + 1, ints) ;;Haskell data Chain = Link Int (Int -> Chain) ints :: Int -> Chain ints n = Link (n+1) ints

1 0

Haskell in 3 Slides
by John Van Enk 19 May '09

19 May '09

Hi all, I'm giving a presentation to an IEEE group on Embedded DSL's and Haskell at the end of June. I need a 3 to 4 slide introduction to Haskell. What suggestions does the community have? Is such a short intro possible? It just needs to introduce the basics so I can show some code without alienating the audience. I'm hoping some one else has attempted this before, but if not, some boiler plate slides could be useful for every one! -- /jve

10 16

ANN: Hieroglyph-2.21 and buster, buster-gtk, and buster-network-2.0
by Jeff Heard 19 May '09

19 May '09

Tons of relevant changes. Almost too many to count... Buster: - Fixed performance and bugs in buster, - split out buster, buster-network, and buster-gtk to make it easier to only build components of the system. - Added new functions in buster for selection and debugging. - Added behaviours in App.Behaviours.PrintEvents for printing only based on Group / Source / Name - Changed name to "ename" (for 'event name') - Added Association Lists to the buster EData type (EAssoc, EAssocL) - future now requires the bus to be passed as the first argument Hieroglyph - OpenGL-backended interactive buster is now functional and high performance if not complete. - Added "Dots" primitive for showing lots of points for things like scatterplots - Got rid of creating Attributes objects in favor of modifying common attributes with combinators; the combinators themselves have the same name as the old attributes, but they are mostly undocumented otherwise because I haven't had time yet. They are found in Graphics.Rendering.Hieroglyph.Visual - Got rid of greater/less detail combinator - Text now takes Text.PrettyPrint.Doc instead of String as the str, accepts Pango markup language, and uses full Layout functionality from Pango, including UTF-8 display. Added Pango markup combinators for Text.PrettyPrint.Docs, mark, bold, bigger, italic, strikethrough, subscript, superscript, smaller, monospace, underline, and span. See Pango documentation for their effect. - Points and Rects are now sensible instances of Num, Fractional, and Ord - Large scenes are now faster overall - Added object naming combinator to support object selection I will have more deails and examples on the blog soon... -- Jeff

1 0

Re: [Haskell-cafe] tips on using monads
by Claus Reinke 19 May '09

19 May '09

>>> I've got one of those algorithms which "threatens to march off the right edge" (in the words of >>> Goerzen et al). I need something like a State or Maybe monad, but this is inside the IO monad. >>> So I presume I need StateT or MaybeT. However, I'm still (sdlowly) learning about monads from >>> first principles. I thought I might present my code and get some pointers... maybe someone could >>> actually show me how to rewrite it, which would be a neat way to see MaybeT and StateT in >>> action. I'm hoping to get anything from a one-line response to a rewrite of my code. Anything >>> will help. >> >> Perhaps this is useful: >> http://www.haskell.org/haskellwiki/Equational_reasoning_examples#Coding_sty… > I can't quite tell--is that example in the IO monad? Part of my difficulty is that I'm inside IO. > I know how to do this with Maybe, except that I have to combine Maybe and IO (use MaybeT?) It was in the GHC.Conc.STM monad, so yes, it used a MaybeT and Control.Monad.Trans.MonadTrans's lift (btw, the MonadTrans docs only point to [1], but [2] might also be of interest, if rather more compact/terse). Claus [1] http://web.cecs.pdx.edu/~mpj/pubs/springschool.html [2] http://web.cecs.pdx.edu/~mpj/pubs/modinterp.html

1 0

tips on using monads
by Michael P Mossey 19 May '09

19 May '09

I've got one of those algorithms which "threatens to march off the right edge" (in the words of Goerzen et al). I need something like a State or Maybe monad, but this is inside the IO monad. So I presume I need StateT or MaybeT. However, I'm still (slowly) learning about monads from first principles. I thought I might present my code and get some pointers... maybe someone could actually show me how to rewrite it, which would be a neat way to see MaybeT and StateT in action. I'm hoping to get anything from a one-line response to a rewrite of my code. Anything will help. Here's the program: {- This is a program which starts with a document containing "notes" about software requirements (in a particular format) and puts them into a database. Notes include details such as the "source" of the requirement (who gave it), the topic(s) to which it pertains, the date, etc. I have written a parser to take a text document typed up by me during a meeting and parse it into a NoteRecord structure. Here is the structure: -} data NoteRecord = NoteRecord { recordSource :: String, -- Name of person who gave req. recordDate :: [Int], -- Date in [<year>,<month>,<date>] recordSourceType :: String, -- "meeting", "phone", "email", etc. recordBugNum :: Maybe Int, -- Bugzilla # (if relevant) recordTopics :: [String], -- list of official topics pertaining recordText :: String } -- the text of the note itself deriving (Show) {- One other wrinkle. The source (person name) and topic must be one of a set of pre-determined strings. A person has an official full name which is stored in the database. Topics also have official descriptive strings. If I wasn't clever, then the note, as I type it up, must have the exact name and topic. But I hate trying to remember things like that. So I have implemented a "fuzzy string match" system so that I can type part of someone's name (or even misspell it) or part of a topic string, and the system will find the best match to an official string. In pseudocode, the function to insert a note in the database must do this: This function starts with a NoteRecord. - If text already exists in the database, give an error and skip to end. - Fuzzy-match strings to topics and source. - If no potential match can be found to some of topics or source, give error and skip to end. - Ask user to confirm if the matched topics and source look okay. - if user says no, skip to end. - Actually insert the record. -} insertNote :: NoteRecord -> Connection -> IO () insertNote nr conn = do -- Check if it exists in the database already. status <- checkPreExistingText nr conn if status then putStrLn "Skipping... text exists already." else do -- Find best fit for all topics and source. -- See type signatures below. bestFitTopics <- fitTopics nr conn bestFitSource <- fitSource nr conn case any isNothing bestFitTopics of True -> putStrLn "Error... some topic couldn't be matched." False -> case bestFitSource of Nothing -> putStrLn "Error.. source couldn't be matched." _ -> do b <- isUserOkay nr bestFitTopics bestFitSource if b then do -- Create a new NoteRecord with matched -- and validated topics/source. nrValidated = nr { recordTopics = bestFitTopics , recordSource = bestFitSource } insertRow nrValidated conn else putStrLn "Abort due to user request." checkPreExistingText :: NoteRecord -> Connection -> Bool -- There are multiple topics in the NoteRecord. For each one, -- find the best fuzzy match, or indicate if there is no plausible -- match at all. fitTopics :: NoteRecord -> Connection -> [Maybe String] -- There is one source. Try to find fuzzy match. fitSource :: NoteRecord -> Connection -> Maybe String -- Present user with all fuzzy matches and get a yes/no response if it's -- okay to proceed. isUserOkay :: NoteRecord -> [Maybe String] -> Maybe String -> Bool -- Do actual insert into database. insertRow :: NoteRecord -> Connection -> IO ()

4 3

Trying to Express Constraints using a data structure
by Günther Schmidt 19 May '09

19 May '09

Hi all, I'm trying to express a constraint using a data structure. Let's say I'd want to express a "mapping" of a to b, c to b, d to b and e to f. A mapping can also be from a to a, b to b and so on. The constraint is that one cannot map a to b if b was already "mapped" to let's say c. I'd like to express this constraint in a data structure, but haven't figured out how, yet. Any suggestions? Günther

2 1