- Haskell-Cafe - Haskell.org

Please help me spot where space leak occur.
by Olexander Kozlov 28 Jul '11

28 Jul '11

Greetings Haskell community, I stuck with a space leak problem in simple task. I have a function described with a list of pairs: type Fn a b = [(a, b)] mapping values from a to b. And I have a composition operation which accepts two functions and returns theirs composition: compose :: Eq b => Fn a b -> Fn b c -> Fn a c Finding composition of 1,000,000 functions takes about 240M with the following implementation: type Fn a b = [(a, b)] lkup :: Eq a => a -> Fn a b -> b lkup x ((a, b) : abs) = if x /= a then lkup x abs else b compose :: Eq b => Fn a b -> Fn b c -> Fn a c compose ((a, b) : abs) bcs = (a, lkup b bcs) : compose abs bcs compose [] _ = [] fldl :: (a -> b -> a) -> a -> [b] -> a fldl f z (x:xs) = fldl f (f z x) xs fldl _ z [] = z fna = [(1, 2), (2, 3), (3, 1)] fni = [(1, 1), (2, 2), (3, 3)] test = fldl compose fni (replicate 1000000 fna) main = print test I build with: ghc --make -prof -auto-all -caf-all -fforce-recomp -rtsopts Test.hs Profile results: Test.exe +RTS -K50M -p -RTS total time = 0.34 secs (17 ticks @ 20 ms) total alloc = 240,003,820 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc compose Main 58.8 80.0 lkup Main 35.3 0.0 test Main 5.9 11.7 fldl Main 0.0 8.3 After reading 'High-Performance Haskell' by Johan Tibell I tried to made my compose function strict: compose :: Eq b => Fn a b -> Fn b c -> Fn a c compose ((a, b) : abs) bcs = let c = lkup b bcs in c `seq` (a, c) : compose abs bcs compose [] _ = [] and memory consuption reduced down to 180M. Good achievement but still too much! Profile results: Test.exe +RTS -K50M -p -RTS total time = 0.24 secs (12 ticks @ 20 ms) total alloc = 180,003,820 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc compose Main 83.3 73.3 lkup Main 8.3 0.0 fldl Main 8.3 11.1 test Main 0.0 15.6 I tried to make fldl strict as well: fldl :: (a -> b -> a) -> a -> [b] -> a fldl f z (x:xs) = let z' = f z x in z' `seq` fldl f z' xs fldl _ z [] = z and end up with 160M of total allocations. Profile results: Test.exe +RTS -K32M -p -RTS total time = 0.30 secs (15 ticks @ 20 ms) total alloc = 160,003,820 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc compose Main 46.7 82.5 lkup Main 40.0 0.0 test Main 6.7 17.5 fldl Main 6.7 0.0 Please help me spot where space leak occur, I see no other places for space leaks. I'll appreciate any help. (I intentionally wrote my own implementations of lookup and foldl to have direct control on them.)

2 3

Ur tutorial, and a challenge
by Adam Chlipala 28 Jul '11

28 Jul '11

Last week, I posted a message to this list looking for people interested in joining projects using my domain-specific language Ur/Web. Some responses rightly chastised me for the lack of documentation on the core Ur language's novel type system features. I'm sure many Haskellers have had the experience of quickly grokking the interfaces of new libraries by reading their type signatures, and I think the same is true for Ur. So, to provide that initial bump of background that should help folks get started, I've begun an Ur tutorial: http://www.impredicative.com/ur/tutorial/ The chapters that are already there are intended to be sufficient to help any experienced Haskell programmer get started quickly with Ur/Web. In particular the second chapter on type-level programming may be of interest as a mind expander, even for folks who don't want to use Ur/Web. I'd love feedback about weaknesses in the tutorial! I also want to attach a challenge to this tutorial, as an expansion to an answer I gave earlier about why Ur/Web needs a new programming language and can't just be implemented as a Haskell library. Consider this online Ur/Web demo: http://www.impredicative.com/ur/demo/crud1.html The example involves a library component encapsulating functionality like that of Ruby on Rails's scaffolding: automatic generation of a standard web-based "admin interface" to an SQL database table. The Ur/Web version uses static typing to guarantee that any applications generated by this component are free of injection attacks and other generic problems. The guarantees apply both to app communication with server-side pieces (e.g., static type-checking of SQL) and client-side pieces (e.g., static type-checking of HTML). This is not done by type-checking individual invocations of the admin-interface component. Rather, the component is checked at a static type which guarantees correct operation for _any_specialization_parameters_. So, the challenge is, can this functionality be implemented in Haskell (GHC extensions fair game, any web framework allowed)? If so, how pretty is it? :)

4 5

Idiomatic ways to make all instances of a certain class also instances of another?
by Tim Cowlishaw 28 Jul '11

28 Jul '11

Hi all, I'm currently embarking on my first major project in Haskell, after dabbling with it for several years, and seem to keep finding myself in situations where I create a typeclass that seems to be some sort of specialisation of another, more general typeclass. Given that this is the case, I've then decided that all instances of the specific class should therefore also be instances of the general class, and arrived at the following method of doing so, using the FlexibleInstances and UndecidableInstances extensions to GHC: {-# LANGUAGE FlexibleInstances, UndecidableInstances #-} class Max a where maximum :: a -> a -> a instance (Ord a) => Max a where maximum = max (Obviously, this is a very trivial, and rather silly example - I'm not really trying to implement a class called 'Max'). However, I'd be curious to know if (a) There are better or more idiomatic ways of achieving the same effect, and (b) Whether or not I should be doing this at all; It did occur to me that this seems rather trying to re-implement OOP-style inheritance with typeclasses, and therefore perhaps not a very Haskellish approach to designing software. Therefore - are there better ways to achieve this, or should I not be doing this at all, and, if the latter, what would be the best means of achieving a similar result (i.e. a typeclass that implements all the functionality of one or more others, optionally with some additional specialism)? Many thanks, Tim

5 7

Fwd: C9 video in the Monadic Design Patterns for the Web series
by Greg Meredith 28 Jul '11

28 Jul '11

Dear Haskellians, A new C9 video in the series! So, you folks already know most of this... except for maybe the generalization of the Conway construction! Best wishes, --greg ---------- Forwarded message ---------- From: Charles Torre <...> Date: Tue, Jul 26, 2011 at 1:12 PM Subject: C9 video in the Monadic Design Patterns for the Web series To: Meredith Gregory <lgreg.meredith(a)gmail.com> Cc: Brian Beckman <...> And we’re live!**** ** ** http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic… **** C**** ** ** *From:* Charles Torre *Sent:* Tuesday, July 26, 2011 11:51 AM *To:* 'Meredith Gregory' *Cc:* Brian Beckman *Subject:* C9 video in the Monadic Design Patterns for the Web series**** ** ** Here it ‘tis:**** ** ** Greg Meredith <http://biosimilarity.blogspot.com/>, a mathematician and computer scientist, has graciously agreed to do a C9 lecture series covering monadic design principles applied to web development. You've met Greg before in a Whiteboard jam session with Brian Beckman<http://channel9.msdn.com/shows/Going+Deep/E2E-Whiteboard-Jam-Session-with-B…> .**** The fundamental concept here is the monad, and Greg has a novel and conceptually simplified explanation of what a monad is and why it matters. This is a very important and required first step in the series since the whole of it is about the application of monadic composition to real world web development.**** In *part 4, *Greg primarily focuses on the idea that *a monad is really an API* -- it's a view onto the organization of data and control structures, not those structures themselves. In OO terms, it's an *interface*. To make this point concrete Greg explores one of the simplest possible data structures that supports at least two different, yet consistent interpretations of the same API. The structure used, Conway's partisan games<http://mathworld.wolfram.com/ConwayGame.html>, turned out to be tailor-made for this investigation. Not only does this data structure have the requisite container-like shape, it provided opportunities to see just what's necessary in a container to implement the monadic interface. ** ** Running throughout the presentation is a more general comparison of reuse between an OO approach versus a more functional one. When the monadic API is "mixed into" the implementing structure we get less reuse than when the implementing structure is passed as a type parameter. Finally, doing the work put us in a unique position to see not just how to generalize Conway's construction, *monadically*, but the underlying pattern which allows the generalization to suggest itself.**** See *part 1 <http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic…> *See *part 2<http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic…> ** *See* part 3<http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic…> ***** ** -- L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW Seattle, WA 98136 +1 206.650.3740 http://biosimilarity.blogspot.com -- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com

3 5

Approximate String Matching
by dokondr 28 Jul '11

28 Jul '11

Hi, I am looking for Haskell libraries to do approximate string matching: http://en.wikipedia.org/wiki/Approximate_string_matching I need this to reduce a set of English word variants with spelling errors to a single canonical dictionary entry. Any libraries to work with spelling will also help. Thanks, Dmitri

2 1

Stack space overflow in HaskellNet
by Manfred Lotz 28 Jul '11

28 Jul '11

Hi there, If I take example imap.hs import System.IO import Network.HaskellNet.IMAP import Text.Mime import qualified Data.ByteString.Char8 as BS import Control.Monad -- the next lines were changed to fit to my local imap server imapServer = "imap.mail.org" user = "" pass = "" main = do con <- connectIMAP imapServer login con user pass mboxes <- list con mapM print mboxes select con "INBOX" msgs <- search con [ALLs] mapM_ (\x -> print x) (take 4 msgs) forM_ (take 4msgs) (\x -> fetch con x >>= print) and change the last line (in order to print all messages of the mailbox) into: forM_ msgs (\x -> fetch con x >>= print) I get Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. Is this something to be fixed in the HaskellNet code, or in the example code? -- Manfred

6 13

Question re SMTPClient
by Jayakumar Ramanathan 28 Jul '11

28 Jul '11

How does one pass authentication info to the SMTP server when using the package STMPClient? Thanks! Jay

1 0

Typeclasses, data, constructors
by Sergiy Nazarenko 27 Jul '11

27 Jul '11

Hi everyone! I have data declaration like this: data MyTable = MyTableOne Int String | MyTableTwo Int String String and function that insert new row in tables: newRow :: MyTable -> IO Int newRow (MyTableOne fld1 fld2 ) = ..... newRow (MyTableTwo fld1 fld2 fld3 ) = ...... That work perfectly, I enjoy it. But now I want to get rows, and I don't know what to do :( I want func something like this: getRow :: Int -> [MyTable] .... - what should I write here ? Possibly use this function: getRow 23 :: MyTableTwo (like haskell function Read for example: read "7" :: Int) I try to use typeclasses, class GetRow a where hasID :: Int -> IO a instance GetRow MyTableOne where hasID myid = return [(MyTableOne 1 "name")] instance GetRow MyTableTwo where hasID myid = return [(MyTableTwo 1 "name" "path")] But I have error: Not in scope: type constructor or class `MyTableOne' make: *** [Foo.so] Error 1 Not in scope: type constructor or class `MyTableTwo' make: *** [Foo.so] Error 1 I ask you to suggest me right way in my efforts Cheers!

2 1

file splitter with enumerator package
by Eric Rasmussen 27 Jul '11

27 Jul '11

Hi everyone, A friend of mine recently asked if I knew of a utility to split a large file (4gb in his case) into arbitrarily-sized files on Windows. Although there are a number of file-splitting utilities, the catch was it couldn't break in the middle of a line. When the standard "why don't you use Linux?" response proved unhelpful, I took this as an opportunity to write my first program using the enumerator package. If anyone has time, I'm really interested in knowing if there's a better way to take the incoming stream and output it directly to a file. The basic steps I'm taking are: 1) Data.Enumerator.Binary.take -- grabs the user-specified number of bytes, then (because it returns a lazy ByteString) I use Data.ByteString.Lazy.hPut to output the chunk 2) Data.Enumerator.Binary.head -- after using take for the big chunk, it inspects and outputs individual characters and stops after it outputs the next newline character 3) I close the handle that steps 1&2 used to output the data and then repeat 1&2 with the next handle (an infinite lazy list of filepaths like part1.csv, part2.csv, and so on) The full code is pasted here: http://hpaste.org/49366, and while I'd like to get any other feedback on how to make it better, I want to note that I'm not planning to release this as a utility so I wouldn't want anyone to spend extra time performing a full code review. Thanks! Eric

5 13

Library for Sparse Vectors?
by dokondr 27 Jul '11

27 Jul '11

Hi, Can't find on hackage any sparse vector library. Does such thing exist? I need efficient storage and dot product calculation for very sparse vectors with about 10 out of 40 000 non-zero components. One solution would be to represent Sparse Vector as Data.Map with (component_index, component_value) pairs to store non-zero components of the vector. In this case, for example, calculating cosine similarity ( http://en.wikipedia.org/wiki/Cosine_similarity) for for every pair of 10 000 vectors, would not be very nice and efficient, I am afraid. Thanks!

3 5