- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] attoparsec double precision, quickCheck and aeson
by Doug McIlroy 11 Jun '12

11 Jun '12

> Date: Tue, 5 Jun 2012 10:25:26 -0700 > From: Warren Harris <warrensomebody(a)gmail.com> > > On Jun 5, 2012, at 9:57 AM, Johan Tibell wrote: > >> I don't think applying == to something that contains floating point >> values at the leaves makes much sense. You want some approxEq function >> that uses approximate equality on floating point value or you want to >> equality function that ignores the floating point values. Probably not >> the answer you like, but I don't know how to define Eq in a robust way >> for types that include floating point values. > > I buy that in general for comparing floats (those that result from arithmetic operations), but this is a case where attoparsec's parser is munging the value. I would like to have a law that says "parse . print == id" ... which is why this seems more like a bug than the usual floating point concerns. This law seems to hold for haskell's double parser: quickCheck (\d -> read (show d) == d) > > Date: Tue, 5 Jun 2012 10:51:08 -0700 > From: "Bryan O'Sullivan" <bos(a)serpentine.com> > > If you need the full precision, use rational instead. The double parser is > there because parsing floating point numbers is often a bottleneck, and > double intentionally trades speed for precision. If I understand the intended meaning of "parse" correctly, what's at issue is decimal-to-binary conversion. It is hard to defend sloppy answers for such a fundamental operation. The recommendation of rational calculation makes little sense for most floating-point computation, which approximates irrationals. The necessary imprecision, though, does not justify sloppiness--and especially not sloppy tests. It's worth noting that a "law" of input being inverse to output must fail, though rarely. Different granularity of the two bases means that there must exist cases where adjacent values in one base convert to the same value in the other. (Conceivably the specialization to parse.print could hold for some hardware. Does anybody know whether the wish is actually hopeless?) Last I looked (admittedly quite a while ago), the state of the art was strtod in http://www.netlib.org/fp/dtoa.c. (Alas, dtoa.c achieves calculational perfection via a murmuration of #ifdefs.) It's disheartening to hear that important Haskell code has needlessly fallen from perfection--perhaps even deliberately. Doug McIlroy

3 4

High memory usage with 1.4 Million records?
by Andrew Myers 11 Jun '12

11 Jun '12

Hi Cafe, I'm working on inspecting some data that I'm trying to represent as records in Haskell and seeing about twice the memory footprint than I was expecting. I've got roughly 1.4 million records in a CSV file (400M on disk) that I parse in using bytestring-csv. bytestring-csv returns a [[ByteString]] (wrapped in `type`s) which I then convert into a list of records that have the following structure: > 3 Int > 1 Text Length 3 > 1 Text Length 11 > 12 Float > 1 UTCTime All fields are marked strict and have {-# UNPACK #-} pragmas (I'm guessing that doesn't do anything for non primitives). (Side note, is there a way to check if things are actually being unpacked?) My back of the napkin memory estimates based on the assumption that nothing is being unpacked (and my very spotty understanding of Haskell data structures): Platform: 64 Bit Linux # Type (Sizeof type (occasionally a guess)) 3 * Int (8) 14 * Char (4) -- Text is some kind of bytestring but I'm guessing it can't be worse than the same number of Char? 12 * Float (4) 18 * sizeOf (ptr) (8) UTC: -- From what I can gather through :info in ghci 4 * (ptr) (8) 2 * Integer (16) -- Shouldn't be overly large, times are within 2012 List: (Pointer to element and next cons cell) 1408113 * 8 * 2 = 2513G + 21.5M So even if the original bytestring file is being kept entirely in memory somehow that's not more than 3G. I've written a small driver test program that just parses the CSV, finds the minimum value for a couple of the Float fields, and exits. In the process monitor the memory usage is 6.9G before the program exits. I've tried profiling with +RTS -hc but it ran for >3 hours without finishing, it normally finishes within 4 minutes. Anyone have any ideas for me? Things to try? Thanks, Andrew

4 5

How to select n random words from a file ...
by Noon Silk 11 Jun '12

11 Jun '12

Hi, I'm clearly new to haskell, and I suppose those is a basic question, but after a bit of searching I've been unable to figure out the "best" way to do this. I was first trying to find out how to, say, get a random element from a list, but I'm starting to think that may not be the best way (because list access isn't constant time, among other reasons). So, I wonder if there is a more direct way to just get a random word from a wordfile (i.e. one word per line) ... can anyone suggest a method? Ideally I'd like to be able to adapt this to get n random words from several files (i.e. randomly select n words from all files; i.e. just read them into one merged array and choose from there?) Thanks for any advice ... -- Noon Silk Fancy a quantum lunch? https://sites.google.com/site/quantumlunch/ "Every morning when I wake up, I experience an exquisite joy — the joy of being this signature."

6 5

Re: [Haskell-cafe] converting functional dependencies to type families
by Henning Thielemann 11 Jun '12

11 Jun '12

On Thu, 7 Jun 2012, Simon Peyton-Jones wrote: > Very useful! Maybe worth turning into a page on the Haskell wiki? I created one: http://www.haskell.org/haskellwiki/Functional_dependencies_vs._type_families

2 2

Haskell User Group Hamburg (Germany) - Meeting Thursday June 14th 2012
by Stefan Schmidt 10 Jun '12

10 Jun '12

Hello cafe, there's an upcomming meeting of the Haskell user group Hamburg next Thursday (June 14th). We'll start 19:00 at the Xing AG in Hamburg (Gänsemarkt 43, 20354 Hamburg). Falko Peters will give a short talk about hedis ( http://hackage.haskell.org/package/hedis) a Redis client written in Haskell. Although this announcement is written in english the talk will be given in german. So if you are interested to come, have a look at our doodle (also in german) and give us a short note if you want to join us. http://www.doodle.com/3fz45uqupp8pzutb Further announcements will be made via Twitter, so you may want to follow https://twitter.com/hug_hh. Stefan Schmidt

1 0

Two parallel libraries from Japan
by Kazu Yamamoto 10 Jun '12

10 Jun '12

Hello cafe, I would like to announce two parallel libraries from Japan. - Paraiso (http://hackage.haskell.org/package/Paraiso) The purpose of this library is to design a high-level language for implementing explicit partial-differential equations solvers on supercomputers as well as today's advanced personal computers. Muranushi-san is also known as the author of Monadius and one of the two translators of "Learn you". - GTALib (http://hackage.haskell.org/package/GTALib) This package provides the core functionalities of the GTA (Generate, Test, and Aggregate) programming framework on Haskell See "Test, and Aggregate - A Calculation-based Framework for Systematic Parallel Programming with MapReduce" for more information. Regards, --Kazu

3 2

ANN: scrobble-0.1.0.1: Scrobbling server
by Christopher Done 10 Jun '12

10 Jun '12

Heyo, If you use Last.fm/Libre.fm you might be interested in running your own local scrobbling server in Haskell. $ cabal update $ cabal install scrobble $ scrobble-server 8910 Source is here with further instructions for audio players and such: https://github.com/chrisdone/scrobble Exactly what the server does with the scrobbles it receives is purely up to you, use it as a library and do as you please. Personally I might work on a Last.fm replacement, at least as far as the statistics/reporting generation goes. Ciao!

1 0

Fundeps and overlapping instances
by Simon Peyton-Jones 09 Jun '12

09 Jun '12

Oleg points out, and Martin also mentions, that functional dependencies appear to interact OK with overlapping instances, but type families do not. I this impression is mistaken, and I'll try to explain why in this message, in the hope of exposing any flaws in my reasoning. We can't permit overlap for type families because it is unsound to do so (ie you can break "well typed programs don't go wrong"). But if it's unsound for type families, it would not be surprising if it was unsound for fundeps too. (I don't think anyone has done a soundness proof for fundeps + local constraints + overlapping instances, have they?) And indeed I think it is. So the short summary of this message is: if it works for fundeps it works for type families, and vice versa. (NB this equivalence is not true about GHC's current implementation, however. GHC doesn't support the combination of fundeps and local constraints at all.) Such an equivalence doesn't argue against fundeps; I'm only suggesting the that the two really are very closely equivalent. I much prefer type families from a programming-style point of view, but that's a subjective opinion. Simon Imagine a system "FDL" that has functional dependencies and local type constraints. The big deal about this is that you get to exploit type equalities in *given* constraints. Consider Oleg's example, cut down a bit: class C a b | a -> b instance C Int Bool newtype N2 a = N2 (forall b. C a b => b) t2 :: N2 Int t2 = N2 True We end up type-checking (True :: forall b. C Int b => b). From the functional dependency we know that (b~Bool), so the function should typecheck. GHC rejects this program; FDL would not. But making use of these extra equalities in "given" constraints is quite tricky. To see why look first at Example 1: module X where class C a b | a -> b data T a where MkT :: C a b => b -> T a module M1 where import X instance C Int Char where ... f :: Char -> T Int f c = MkT c module M2 where import X instance C Int Bool g :: T Int -> Bool g (MkT x) = x module Bad where import M1 import M2 bad :: Char -> Bool bad = g . f This program is unsound: it lets you cast an Int to a Bool; result is a seg-fault. You may say that the problem is the inconsistent functional dependencies in M1 and M2. But GHC won't spot that. For type families, to avoid this we "eagerly" check for conflicts in type-family instances. In this case the conflict would be reported when compiling module Bad, because that is the first time when both instances are visible together. So any FDL system should also make this eager check for conflicts. What about overlap? Here's Example 2: {-# LANGUAGE IncoherentInstances #-} module Bad where import X -- Overlapping instances instance C Int Bool -- Instance 1 instance C a [a] -- Instance 2 f :: Char -> T Int f c = MkT c -- Uses Instance 1 g :: T a -> a g (MkT x) = x -- Uses Instance 2 bad :: Char -> Int bad = g . f Again, a seg fault if it typechecks. But will it? When typechecking 'g', we get a constraint (C a ?), where 'a' is a skolem constant. Without IncoherentInstances GHC would reject the program on the grounds that it does not know what instance to choose. But *with* IncoherentInstances it would probably go through, which is unsound. So IncoherentInstances has moved from causing varying dynamic behaviour to causing seg faults. Very well, so FDL must get rid of IncoherentInstances altogether, at least for classes that have functional dependencies (or that have superclasses that do). But at the moment GHC makes an exception for *existentials*. Consider Example 3: class C a b | a -> b -- Overlapping instances instance C Int Bool -- Instance 1 instance C a [a] -- Instance 2 data T where MkT :: C a b => a -> b -> T f :: Bool -> T f x = MkT (3::Int) x -- Uses Instance 1 g :: T -> T g (MkT n x) = MkT n (reverse x) -- Uses Instance 2 bad :: Bool -> T bad = g . f In the pattern match for MkT in g we have the constraint (C a b), where 'a' is existentially bound. So under GHC's current rules it'll choose the (C a [a]) instance, and conclude that (b ~ [a]). So it's ok to reverse x. But it isn't; see function bad! So to avoid unsoundness we must not choose a particular instance from an overlapping set unless we know, absolutely positively, that the other cases cannot match. (GHC's exception for existentials was introduced in response to user demand. Usually, overlapping instances are somehow semantically coherent, and with an existential we are *never* going to learn more about the instantiating type, so choosing the best available seems like a good thing to do.) But even nuking IncoherentInstances altogether is not enough. Consider this variant of Example 3, call it Example 4: module M where class C a b | a -> b instance C a [a] -- Instance 2 data T where MkT :: C a b => a -> b -> T g :: T -> T g (MkT n x) = MkT n (reverse x) -- Uses Instance 2 module Bad where import M instance C Int Bool -- Instance 1 f :: Bool -> T f x = MkT (3::Int) x -- Uses Instance 1 bad :: Bool -> T bad = g . f This is nasty. In module M we have only one instance declaration for C, so there's no overlap, and function g typechecks fine. Now module Bad adds an overlapping instance declaration and 'f' uses it; moreover, it's clear that the new instance declaration is the right one to use. It's not clear how to fix this. The only way I can think of is to insist that all the instances appear in a single module, so that you cannot add more "later". But that loses part of the point of overlap in the first place, namely to provide a generic instance and then later override it. So FDL must * embody eager checking for inconsistent instances, across modules * never resolve overlap until only a unique instance can possibly match * put all overlapping instances in a single module Type families already implement the first of these. I believe that if we added the second and third, then overlap of type families would be fine. (I may live to eat my words here.) I'd be interested to know what Chameleon does on these examples.

6 18

Re: [Haskell-cafe] Have you seen this functor/contrafunctor combo?
by Edward Kmett 09 Jun '12

09 Jun '12

Here is a considerably longer worked example using the analogy to J, borrowing heavily from Wadler: As J, this doesn't really add any power, but perhaps when used with non-representable functors like Equivalence/Comparison you can do something more interesting. -- Used for Hilbert {-# LANGUAGE DefaultSignatures, TypeOperators #-} -- Used for Representable {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleContexts, FlexibleInstances #-} module Search where import Control.Applicative import Data.Function (on) import Data.Functor.Contravariant import GHC.Generics -- for Hilbert newtype Search f a = Search { optimum :: f a -> a } instance Contravariant f => Functor (Search f) where fmap f (Search g) = Search $ f . g . contramap f instance Contravariant f => Applicative (Search f) where pure a = Search $ \_ -> a Search fs <*> Search as = Search $ \k -> let go f = f (as (contramap f k)) in go (fs (contramap go k)) instance Contravariant f => Monad (Search f) where return a = Search $ \_ -> a Search ma >>= f = Search $ \k -> optimum (f (ma (contramap (\a -> optimum (f a) k) k))) k class Contravariant f => Union f where union :: Search f a -> Search f a -> Search f a instance Union Predicate where union (Search ma) (Search mb) = Search $ \ p -> case ma p of a | getPredicate p a -> a | otherwise -> mb p instance Ord r => Union (Op r) where union (Search ma) (Search mb) = Search $ \ f -> let a = ma f b = mb f in if getOp f a >= getOp f b then a else b both :: Union f => a -> a -> Search f a both = on union pure fromList :: Union f => [a] -> Search f a fromList = foldr1 union . map return class Contravariant f => Neg f where neg :: f a -> f a instance Neg Predicate where neg (Predicate p) = Predicate (not . p) instance Num r => Neg (Op r) where neg (Op f) = Op (negate . f) pessimum :: Neg f => Search f a -> f a -> a pessimum m p = optimum m (neg p) forsome :: Search Predicate a -> (a -> Bool) -> Bool forsome m p = p (optimum m (Predicate p)) forevery :: Search Predicate a -> (a -> Bool) -> Bool forevery m p = p (pessimum m (Predicate p)) member :: Eq a => a -> Search Predicate a -> Bool member a x = forsome x (== a) each :: (Union f, Bounded a, Enum a) => Search f a each = fromList [minBound..maxBound] bit :: Union f => Search f Bool bit = fromList [False,True] cantor :: Union f => Search f [Bool] cantor = sequence (repeat bit) least :: (Int -> Bool) -> Int least p = head [ i | i <- [0..], p i ] infixl 4 --> (-->) :: Bool -> Bool -> Bool p --> q = not p || q fan :: Eq r => ([Bool] -> r) -> Int fan f = least $ \ n -> forevery cantor $ \x -> forevery cantor $ \y -> (take n x == take n y) --> (f x == f y) -- a length check that can handle infinite lists compareLength :: [a] -> Int -> Ordering compareLength xs n = case drop (n - 1) xs of [] -> LT [_] -> EQ _ -> GT -- Now, lets leave Haskell 98 behind -- Using the new GHC generics to derive versions of Hilbert's epsilon class GHilbert t where gepsilon :: Union f => Search f (t a) class Hilbert a where -- http://en.wikipedia.org/wiki/Epsilon_calculus epsilon :: Union f => Search f a default epsilon :: (Union f, GHilbert (Rep a), Generic a) => Search f a epsilon = fmap to gepsilon instance GHilbert U1 where gepsilon = return U1 instance (GHilbert f, GHilbert g) => GHilbert (f :*: g) where gepsilon = liftA2 (:*:) gepsilon gepsilon instance (GHilbert f, GHilbert g) => GHilbert (f :+: g) where gepsilon = fmap L1 gepsilon `union` fmap R1 gepsilon instance GHilbert a => GHilbert (M1 i c a) where gepsilon = fmap M1 gepsilon instance Hilbert a => GHilbert (K1 i a) where gepsilon = fmap K1 epsilon instance Hilbert () instance (Hilbert a, Hilbert b) => Hilbert (a, b) instance (Hilbert a, Hilbert b, Hilbert c) => Hilbert (a, b, c) instance (Hilbert a, Hilbert b, Hilbert c, Hilbert d) => Hilbert (a, b, c, d) instance (Hilbert a, Hilbert b, Hilbert c, Hilbert d, Hilbert e) => Hilbert (a, b, c, d, e) instance Hilbert Bool instance Hilbert Ordering instance Hilbert a => Hilbert [a] instance Hilbert a => Hilbert (Maybe a) instance (Hilbert a, Hilbert b) => Hilbert (Either a b) instance Hilbert Char where epsilon = each instance (Union f, Hilbert a) => Hilbert (Search f a) where epsilon = fmap fromList epsilon search :: (Union f, Hilbert a) => f a -> a search = optimum epsilon find :: Hilbert a => (a -> Bool) -> a find = optimum epsilon . Predicate every :: Hilbert a => (a -> Bool) -> Bool every = forevery epsilon exists :: Hilbert a => (a -> Bool) -> Bool exists = forsome epsilon -- and MPTCs/Fundeps to define representable contravariant functors: class Contravariant f => Representable f r | f -> r where represent :: f a -> a -> r tally :: (a -> r) -> f a instance Representable (Op r) r where represent (Op f) = f tally = Op instance Representable Predicate Bool where represent (Predicate p) = p tally = Predicate supremum :: Representable f r => Search f a -> (a -> r) -> r supremum m p = p (optimum m (tally p)) infimum :: (Representable f r, Neg f) => Search f a -> (a -> r) -> r infimum m p = p (pessimum m (tally p)) A few toy examples: ghci> supremum (fromList [1..10] :: Search (Op Int) Int) id 10 ghci> find (=='a') 'a' ghci> fan (!!4) 5 ghci> find (\xs -> compareLength xs 10 == EQ && (xs !! 4) == 'a') "\NUL\NUL\NUL\NULa\NUL\NUL\NUL\NUL\NUL" -Edward

1 1

ANNOUNCE: optparse-applicative 0.0.1
by Paolo Capriotti 09 Jun '12

09 Jun '12

I'm pleased to announce the release of version 0.0.1 of [optparse-applicative][1], a library for writing command line option parsers in Applicative style. You can find an introduction and tutorial on the [github page][2], and an explanation of the internals on [my blog][3]. [1]: http://hackage.haskell.org/package/optparse-applicative [2]: https://github.com/pcapriotti/optparse-applicative [3]: http://paolocapriotti.com/blog/2012/04/27/applicative-option-parser/ BR, Paolo

1 0