March 2009 - Haskell-Cafe

Re: [Haskell-cafe] serializing large data structures, stack overflow
by Don Stewart 07 Mar '09

07 Mar '09

import Data.Binary and then write a variant of something like how Maps are currently serialised: instance (Ord k, Binary k, Binary e) => Binary (Map.Map k e) where put m = put (Map.size m) >> mapM_ put (Map.toAscList m) get = liftM Map.fromDistinctAscList get So you might want something that avoids flattening it to a list first -- Don frigginfriggins: > can you link to a good example of writing your own because I couldn't find one. > > On Sat, Mar 7, 2009 at 8:57 PM, Don Stewart <dons(a)galois.com> wrote: > > Increase the stack size, or use a different serialiser (they're only a > half dozen lines to write), or different data structure? > > -- Don > > frigginfriggins: > > I'm playing around with Netflix, implementing a simple KNN-algorithm, I > will > > later try SVD which seems to be the most successful approach. > > > > Using a database like Postgresqk is to slow so I want to serialize a > > datastructure containing the ratings. I'm not sure about the > > representation I will use just yet, if I should use multiple arrays or an > Map/ > > IntMap. > > > > However I tried Data.Binary and already for small sizes I get stack > overflow > > when deserializing. > > The serializing works fine but when bringing it back it overflows. > > How can I solve this? This is just 2MB, I will eventually need soemthing > like > > 2-500MB to store everything depending on what representatin I choose. > > > > module Serialize where > > import qualified Data.Binary as B > > import qualified Data.Binary.Put as P > > import qualified Data.Map as M > > import qualified Data.List as L > > > > genTest :: Int -> M.Map (Int,Int) Int > > genTest n = let movies = take n $ repeat 1 > > grades = take n $ repeat 4 in > > M.fromList $ ([1..n] `zip` movies) `zip` grades > > > > main = do > > let a = genTest 50000 > > B.encodeFile "C:/users/saftarn/desktop/bintest.txt" a > > print "Success" > > > > dec = B.decodeFile "C:/users/saftarn/desktop/bintest.txt" >>= \a -> > > return $ (a :: M.Map (Int,Int) Int) > > > > > > > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > >

1 0

Zippers
by Cristiano Paris 07 Mar '09

07 Mar '09

Hi, I'm trying to catch the connection between delimited continuations and zippers so I wrote a (kinda) zipper interface to a simple tree structure. Here's the code: ------- module Main where import Data.Maybe data Tree a = Leaf a | Fork (Tree a) (Tree a) deriving Show tree = Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Fork (Leaf 4) (Leaf 5))) data ZContext a = ZContext { moveUp :: Maybe (ZContext a), moveLeft :: Maybe (ZContext a), moveRight :: Maybe (ZContext a), this :: Maybe a } initZ t = doInitZ Nothing t where doInitZ c (Leaf a) = ZContext c Nothing Nothing $ Just a doInitZ c t@(Fork l r) = ZContext c (Just $ doInitZ s l) (Just $ doInitZ s r) Nothing where s = Just $ doInitZ c t ------- You access the tree in the following way (session from ghci): *Main> this $ fromJust . moveLeft $ fromJust . moveLeft $ initZ tree I read Haskell book's Chapter about Zippers on Wikibooks and I think I understood the underlying concept even if the implementation still seems to me a bit arbitrary (i.e. different implementation can be provided even if the proposed one is neat thinking of differentiation). Hence, I decided to go experimenting myself and came up with the above solution. I know that the interface to a tree having values only on leaves is pointless as the main advantage of using a Zipper is to get O(1) performance on updating but I wanted to keep it as simple as possible. So, can you provide some comments on that implementation? Thank you all, as usual! -- Cristiano

4 8

Running HUnit tests when pushing to darcs on haskell.org
by Colin Paul Adams 07 Mar '09

07 Mar '09

Hello cafe, I've just followed the instructions at http://www.haskell.org/haskellwiki/How_to_write_a_Haskell_program to create my first library project on haskell.org, using darcs. I tried using the darcs setpref test command to execute: runhaskell tests/*.hs (which works locally) but it fails because it can't find Test.HUnit. When I looked back at the webpage, I see it specifically mentions QuickCheck and not HUnit, so I guess I should not have been surprised. But I would like to know if this is possible, and if so, how to arrange that runhaskell can find Test.HUnit. -- Colin Adams Preston Lancashire

1 0

Interesting problem from Bird (4.2.13)
by R J 07 Mar '09

07 Mar '09

Could someone provide an elegant solution to Bird problem 4.2.13? Here are the problem and my inelegant solution: Problem ------- Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive. For example, data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a) The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y. However, since "++" is associative, the expressions "Cat xs (Cat ys zs)" and "Cat (Cat xs ys) zs" should be regarded as equal. Define appropriate instances of "Eq" and "Ord" for "CatList". Inelegant Solution ------------------ The following solution works: instance (Eq a) => Eq (CatList a) where CatNil == CatNil = True CatNil == Wrap z = False CatNil == Cat z w = ( z == CatNil && w == CatNil ) Wrap x == CatNil = False Wrap x == Wrap z = x == z Wrap x == Cat z w = ( Wrap x == z && w == CatNil ) || ( Wrap x == w && z == CatNil ) Cat x y == CatNil = x == CatNil && y == CatNil Cat x y == Wrap z = ( x == Wrap z && y == CatNil ) || ( x == CatNil && y == Wrap z ) Cat x y == Cat z w = unwrap (Cat x y) == unwrap (Cat z w) unwrap :: CatList a -> [a] unwrap CatNil = [] unwrap (Wrap x) = [x] unwrap (Cat x y) = unwrap x ++ unwrap y instance (Eq a, Ord a) => Ord (CatList a) where x < y = unwrap x < unwrap y This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]): Wrap 1 == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1) == Wrap (Cat (Wrap 1) CatNil) Although this solution works, it's a hack, because unwrap converts CatLists to lists. The question clearly seeks a pure solution that does not rely on Haskell's built-in lists. What's the pure solution that uses cases and recursion on CatList, not Haskell's built-in lists, to capture the equality of nested CatLists? _________________________________________________________________ Windows Live™ Contacts: Organize your contact list. http://windowslive.com/connect/post/marcusatmicrosoft.spaces.live.com-Blog-…

6 7

Type question re: map
by R J 06 Mar '09

06 Mar '09

Given the following (usual) definition of "map": map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x : xs) = f x : map f xs What's the type of "map map"? GHCi's :t command reveals: *Main> :t map map map map :: [a -> b] -> [[a] -> [b]] I'd be grateful if anyone could provide a systematic type calculation so that I can reason through more complicated examples myself. Thanks. _________________________________________________________________ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009

3 2

Test if a file is empty or stat in haskell
by Anish Muttreja 06 Mar '09

06 Mar '09

I am looking for a way to test if a file is empty. Something like isFileEmpty along the lines of System.Directory.doesFileExist? A function that wraps stat would also serve the purpose. I get the feeling that someone must have felt the need for this before me, but Google search not yield anything, hence the question. Thanks! Anish

5 6

Re: [Haskell-cafe] Data.Binary stack overflow with Data.Sequence String
by Gwern Branwen 06 Mar '09

06 Mar '09

On Tue, Mar 3, 2009 at 11:50 PM, Spencer Janssen <spencerjanssen(a)gmail.com> wrote: > On Tue, Mar 3, 2009 at 10:30 PM, Gwern Branwen <gwern0(a)gmail.com> wrote: >> So recently I've been having issues with Data.Binary & Data.Sequence; >> I serialize a 'Seq String' >> >> You can see the file here: http://code.haskell.org/yi/Yi/IReader.hs >> >> The relevant function seems to be: >> >> -- | Read in database from 'dbLocation' and then parse it into an 'ArticleDB'. >> readDB :: YiM ArticleDB >> readDB = io $ (dbLocation >>= r) `catch` (\_ -> return empty) >> where r x = fmap (decode . BL.fromChunks . return) $ B.readFile x >> -- We read in with strict bytestrings to guarantee the >> file is closed, >> -- and then we convert it to the lazy bytestring >> data.binary expects. >> -- This is inefficient, but alas... >> >> My current serialized file is about 9.4M. I originally thought that >> the issue might be the recent upgrade in Yi to binary 0.5, but I >> unpulled patches back to past that, and the problem still manifested. >> >> Whenever yi tries to read the articles.db file, it stack overflows. It >> actually stack-overflowed on even smaller files, but I managed to bump >> the size upwards, it seems, by the strict-Bytestring trick. >> Unfortunately, my personal file has since passed whatever that limit >> was. >> >> I've read carefully the previous threads on Data.Binary and Data.Map >> stack-overflows, but none of them seem to help; hacking some $!s or >> seqs into readDB seems to make no difference, and Seq is supposed to >> be a strict datastructure already! Doing things in GHCi has been >> tedious, and hasn't enlightened me much: sometimes things overflow and >> sometimes they don't. It's all very frustrating and I'm seriously >> considering going back to using the original read/show code unless >> anyone knows how to fix this - that approach may be many times slower, >> but I know it will work. >> >> -- >> gwern > > Have you tried the darcs version of binary? It has a new instance > which looks more efficient than the old. > > > Cheers, > Spencer Janssen I have. It still stack-overflows on my 9.8 meg file. (The magic number seems to be somewhere between 9 and 10 megabytes.) -- gwern

3 5

MPI
by FFT 06 Mar '09

06 Mar '09

Are MPI bindings still the best way of using Haskell on Beowulf clusters? It's my feeling that the bindings stagnated, or are they just very mature?

4 6

Re: [Haskell-cafe] Hint and Ambiguous Type issue
by Daniel Gorín 06 Mar '09

06 Mar '09

I think you can achieve what you want but you need to use the correct types for it. Remember that when you write: getFilterMainStuff :: Deliverable a => FilePath -> Interpreter (Path, Filter a) the proper way to read the signature is "the caller of getFilterMainStuff is entitled to pick the type of a, as long as it picks an instance of Deliverable". Contrast this with a method declaration in Java where: public Set getKeys() is to be read: "The invoked object may pick the type of the result, as long as it is a subclass of (or implements) Set". When you say that you want "to apply fMain to a (Config, Email) and get back a Deliverable a", I think you mean that fMain picks the type for a (and has to be an instance of Deliverable). There two ways to do this in Haskell: 1) You don't. If you know that your possible Deliverables are just FlatEmail and MaildirEmail, then the idiomatic way of doing this would be to turn Deliverable into an ADT: data Deliverable = FlatEmail .... | MaildirEmail .... deriving (Typeable) getFilterMainStuff :: FilePath -> Interpreter (Path, Filter Deliverable) 2) Existential types. If, for some reason, you need your "dynamic code" to be able to define new "deliverables", then you need to use the extension called "existential types". -- using GADT syntax data SomeDeliverable where Wrap :: Deliverable a => a -> SomeDeliverable getFilterMainStuff :: FilePath -> Interpreter (Path, Filter SomeDeliverable) This basically resembles the contract of the Java world: if you run fMain you will get a value of type SomeDeliverable; you can pattern- match it and will get something whose actual type you don't know, but that it is an instance of class Deliverable. See http://www.haskell.org/haskellwiki/Existential_type Good luck! Daniel On Mar 6, 2009, at 2:33 AM, Joseph Fredette wrote: > Okay, I think I understand... I got so hung up thinking the error > had to be in the Interpreter code, I didn't bother to look in the > caller... > > But every answer breeds another question... The practical reason for > inferring fMain as being of type "Deliverable a => Filter a", is to > apply it (via runReader) to a (Config, Email) and get back a > Deliverable a, then to use the deliverIO method on the result -- my > question is, it appears I have to "know" the specific type of a in > order to get the thing to typecheck, but in order to use it, I need > to not know it... > > Perhaps, in fact, I'm doing this wrong. Thanks for the help Daniel, > everyone... > > /Joe > > Daniel Gorín wrote: >> Ok, so I've pulled the latest version and the error I get now is: >> >> Hackmain.hs:70:43: >> Ambiguous type variable `a' in the constraint: >> `Deliverable a' >> arising from a use of `getFilterMainStuff' at Hackmain.hs: >> 70:43-60 >> Probable fix: add a type signature that fixes these type >> variable(s) >> >> Function getFilterMainStuff compiles just fine . The offending line >> is in buildConf and reads: >> >> > (inboxL, fMain) <- runUnsafeInterpreter . getFilterMainStuff $ >> filterMainL >> >> The problem is that GHC can't figure out the type of fMain. It >> infers (Filter a), but doesn't know what is a and therefore how to >> build a proper dictionary to pass to getFilterMainStuff. >> >> Observe that you would get a similar error message if you just >> defined: >> >> > f = show . read >> >> I can get it to compile by providing a type annotation for fMain: >> >> > (inboxL, fMain) <- runUnsafeInterpreter . getFilterMainStuff $ >> filterMainL >> > let _ = fMain :: Filter MaildirEmail >> >> So once you use fMain somewhere and GHC can infer it's type, >> everything should work fine. >> >> Daniel >> >> On Mar 5, 2009, at 11:26 PM, Joseph Fredette wrote: >> >>> Oh, crap- I must have never pushed the latest patches, I did put >>> the typeable instances in all the appropriate places. And provided >>> a (maybe incorrect? Though I'm fairly sure that shouldn't affect >>> the bug I'm having now) Typeable implementation for Reader, but I >>> still get this ambiguous type. I'll push the current version asap. >>> >>> Thanks. >>> >>> /Joe >>> >>> Daniel Gorín wrote: >>>> Hi >>>> >>>> I've downloaded Hackmain from patch-tag, but I'm getting a >>>> different error. The error I get is: >>>> >>>> Hackmain.hs:63:10: >>>> No instance for (Data.Typeable.Typeable2 >>>> Control.Monad.Reader.Reader) >>>> arising from a use of `interpret' at Hackmain.hs:63:10-67 >>>> >>>> Hint requires the interpreted values to be an instance of >>>> Typeable in order to check, in runtime, that the interpreted >>>> value matches the type declared at compile. Therefore, you need >>>> to make sure that (Filter a) is indeed an instance of Typeable. >>>> >>>> Since you have Filter a = Reader (Config, Email) a, you probably >>>> need to >>>> >>>> - Derive Config and Email instances for Filter, >>>> >>>> - Manually provide Typeable instances for Reader a b, something >>>> along the lines of: >>>> >>>> instance (Typeable a, Typeable b) => Typeable (Reader a b) where... >>>> >>>> (I don't know why this isn't done in the mtl....) >>>> >>>> - Change the signature to: >>>> >>>> getFilterMain :: (Typeable a, Deliverable a) => FilePath -> >>>> Interpreter (Filter a) >>>> >>>> Also, you can try using "infer" instead of "as :: ...." >>>> >>>> Hope that helps >>>> >>>> Daniel >>>> >>>> On Mar 5, 2009, at 8:47 PM, Joseph Fredette wrote: >>>> >>>>> So, I tried both of those things, both each alone and together. >>>>> No dice. Same error, so I reverted back to the >>>>> original. :( >>>>> However, I was, after some random type signature insertions, >>>>> able to convert the problem into a different one, via: >>>>> >>>>> getFilterMain :: Deliverable a => FilePath -> Interpreter >>>>> (Filter a) getFilterMain MainLoc = do >>>>> loadModules [fMainLoc]; setTopLevelModules [(takeWhile (/ >>>>> ='.') fMainLoc)] fMain <- >>>>> (interpret "(filterMain)" infer) >>>>> return (fMain :: Deliverable a => Filter a) >>>>> >>>>> Inferred type is less polymorphic than expected >>>>> Quantified type variable `a' is mentioned in the environment: >>>>> fMain :: Filter a (bound at Hackmain.hs:77:1) >>>>> In the first argument of `return', namely >>>>> `(fMain :: (Deliverable a) => Filter a)' >>>>> In the expression: return (fMain :: (Deliverable a) => Filter a) >>>>> In the expression: >>>>> do loadModules [fMainLoc] >>>>> setTopLevelModules [(takeWhile (/= '.') fMainLoc)] >>>>> fMain <- (interpret "(filterMain)" infer) >>>>> return (fMain :: (Deliverable a) => Filter a) >>>>> I'm >>>>> thinking that this might be more easily solved -- I do think I >>>>> understand the issue. somehow, I need to tell the compiler >>>>> that the 'a' used in the return statement (return >>>>> (fMain :: ...)) is the same as the 'a' in the type sig for the >>>>> whole function. >>>>> >>>>> While I ponder this, and hopefully receive some more help -- >>>>> thanks again Dan, Ryan -- Are there any other options besides >>>>> Hint that might -- at least in the short term -- make this >>>>> easier? I'd really like to finish this up. I'm _so_ close to >>>>> getting it done. >>>>> >>>>> Thanks, >>>>> >>>>> /Joe >>>>> >>>>> Ryan Ingram wrote: >>>>>> So, by using the Haskell interpreter, you're using the >>>>>> not-very-well-supported dynamically-typed subset of Haskell. >>>>>> You can >>>>>> tell this from the type signature of "interpret": >>>>>> >>>>>> >>>>>>> interpret :: Typeable a => String -> a -> Interpreter a >>>>>>> >>>>>> >>>>>> >>>>>>> as :: Typeable a => a >>>>>>> as = undefined >>>>>>> >>>>>> >>>>>> (from http://hackage.haskell.org/packages/archive/hint/0.2.1/doc/html/src/Languag…) >>>>>> >>>>>> In particular, the "as" argument to interpret is specifying >>>>>> what type >>>>>> you want the interpreted result to be typechecked against; the >>>>>> interpretation fails if it doesn't match that type. But you >>>>>> need the >>>>>> result type to be an instance of Typeable; (forall a. >>>>>> Deliverable a => >>>>>> Filter a) most certainly is not. >>>>>> >>>>>> >>>>>> Off the top of my head, you have a couple of directions you can >>>>>> take this. >>>>>> >>>>>> (1) Make Typeable a superclass of Deliverable, saying that all >>>>>> deliverable things must be dynamically typeable. Then derive >>>>>> Typeable >>>>>> on Filter, and have the result be of type "Filter a" using >>>>>> ScopedTypeVariables as suggested before. (You can also pass >>>>>> "infer" to >>>>>> the interpreter and let the compiler try to figure out the >>>>>> result type >>>>>> instead of passing (as :: SomeType).) >>>>>> >>>>>> (2) Make a newtype wrapper around Filter and give it an >>>>>> instance of >>>>>> Typeable, and add a constraint to filterMain that the result >>>>>> type in >>>>>> the filter is also typeable. Then unwrap the newtype after the >>>>>> interpreter completes. >>>>>> >>>>>> Good luck; I've never tried to use the Haskell interpreter >>>>>> before, so >>>>>> I'm curious how well it works and what problems you have with it! >>>>>> >>>>>> >>>>>> -- ryan >>>>>> >>>>>> 2009/3/5 Joseph Fredette <jfredett(a)gmail.com>: >>>>>> >>>>>>> I've been working on a little project, and one of the things I >>>>>>> need to do is >>>>>>> dynamically compile and import a Haskell Source file >>>>>>> containing filtering >>>>>>> definitions. I've written a small monad called Filter which is >>>>>>> simply: >>>>>>> >>>>>>> type Filter a = Reader (Config, Email) a >>>>>>> >>>>>>> To encompass all the email filtering. The method I need to >>>>>>> import, >>>>>>> filterMain, has type: >>>>>>> >>>>>>> filterMain :: Deliverable a => Filter a >>>>>>> >>>>>>> where Deliverable is a type class which abstracts over >>>>>>> delivery to a path in >>>>>>> the file system. The notion is that I can write a type like: >>>>>>> >>>>>>> data DEmail = {email :: Email, path :: FilePath} >>>>>>> newtype Maildir = MD DEmail >>>>>>> >>>>>>> instance Deliverable Maildir where >>>>>>> {- ... omitted -} >>>>>>> >>>>>>> However, Filter a should not be restricted to Deliverable >>>>>>> types- it also >>>>>>> encompasses the results of regular expression matching, etc, >>>>>>> which are not >>>>>>> -- in general -- Deliverable instances. >>>>>>> >>>>>>> My question is this, when importing the file containing the >>>>>>> definitions of >>>>>>> filterMain, I have the following code to grab filterMain and >>>>>>> return it as a >>>>>>> function. >>>>>>> >>>>>>> getFilterMain :: Deliverable a => FilePath -> Interpreter >>>>>>> (Filter a) >>>>>>> getFilterMain fMainLoc = do >>>>>>> loadModules >>>>>>> [fMainLoc]; setTopLevelModules [(takeWhile (/='.') fMainLoc)] >>>>>>> fMain <- (interpret "(filterMain)" (as :: >>>>>>> Deliverable a >>>>>>> => Filter a)) return (fMain) >>>>>>> >>>>>>> However, when I try to >>>>>>> compile >>>>>>> this, I get the type error: >>>>>>> >>>>>>> Hackmain.hs:70:43: >>>>>>> Ambiguous type variable `a' in the constraint: >>>>>>> `Deliverable a' >>>>>>> arising from a use of `getFilterMainStuff' at >>>>>>> Hackmain.hs:70:43-60 >>>>>>> Probable fix: add a type signature that fixes these type >>>>>>> variable(s) >>>>>>> >>>>>>> My understanding is that a type like "Foo a => Bar a" (where >>>>>>> Foo is a class >>>>>>> and Bar is a datatype) would simply restrict >>>>>>> the values of a to only those implementing Foo. But evidently >>>>>>> I'm wrong. Is >>>>>>> there a good (read, easy... :) ) fix to this? >>>>>>> >>>>>>> Any help would be greatly appreciated. >>>>>>> >>>>>>> /Joe >>>>>>> >>>>>>> PS. All the actual code is on patch-tag, here >>>>>>> http://patch-tag.com/repo/Hackmail/home -- if anyone prefers >>>>>>> to look at that >>>>>>> directly, the relevant files are in Src, namely, Hackmain.hs, >>>>>>> Filter.hs, and >>>>>>> Deliverable.hs >>>>>>> >>>>>>> _______________________________________________ >>>>>>> Haskell-Cafe mailing list >>>>>>> Haskell-Cafe(a)haskell.org >>>>>>> http://www.haskell.org/mailman/listinfo/haskell-cafe >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>> <jfredett.vcf>_______________________________________________ >>>>> Haskell-Cafe mailing list >>>>> Haskell-Cafe(a)haskell.org >>>>> http://www.haskell.org/mailman/listinfo/haskell-cafe >>>> >>>> >>> <jfredett.vcf> >> >> > <jfredett.vcf>

2 1

Re: Migration to QuickCheck 2.0
by John Goerzen 06 Mar '09

06 Mar '09

John Goerzen wrote: > Hi, > > My google skills must be faulty, because I can't find much stuff on > migrating from QuickCheck 1.0 to 2.0. > > I've got a number of questions: > > What's the deal with Result and reason being in two different places > in QuickCheck with two different definitions? > > All the QC.Config -- configMaxTest, defaultConfig, arguments, etc. are > missing. Are there direct replacements? OK, ignore the second one. That was an HUnit question; sorry. > > Thanks, > > -- John

1 0