June 2012 - Haskell-Cafe

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

ANN: lucienne-0.0.1
by Alexander Bau 09 Jun '12

09 Jun '12

Hi, some time ago I wrote lucienne[1] using the happstack framework: > Lucienne is a simple server side feed aggregator/reader that helps > you managing your subscribed feeds. It provides multi user support > using basic access authentication. A running mongoDB serves as > database backend. For more information, check [1] and [2]. Best regards, Alex [1] http://hackage.haskell.org/package/lucienne [2] http://www.imn.htwk-leipzig.de/~abau/lucienne

1 0

I don't understand how ST works
by Nicu Ionita 09 Jun '12

09 Jun '12

Hi, After trying the whole afternoon to make a program work using ST and mutable vectors, I must give up and ask for some help. I have a pure function which generates a list of moves. But the whole thing should live in the ST monad, so: > genMoves ... = runST $ do ... Now, as I understand, I have a private universe (under runST) in which I can run "impure code", from which nothing escapes to the outside. Now in that universe I prepare succesively (and use later) a data structure which contains pure and impure values, for example: > data MList = MList { mlVec :: MVector s Move, mlNextPh :: MList -> ST s (Maybe MList) } Now comes my question: in the impure values there is always that "s". I was thinking that the whole structure should have s as a parameter: > data MList s = MList { mlVec :: MVector s Move, mlNextPh :: MList -> ST s (Maybe (MList s)) } but then, when I define functions like: > splitMove :: MList s -> ST s (Maybe (Move, MList s)) > splitMove ml = do > m <- unsafeRead (mvVec ml) 0 > ... I get this message: Moves\MoveList.hs:217:28: Couldn't match type `s' with `PrimState (ST s)' `s' is a rigid type variable bound by the type signature for splitMove :: MList s -> ST s (Maybe (Move, MList s)) at Moves\MoveList.hs:210:1 Expected type: U.MVector (PrimState (ST s)) Move Actual type: U.MVector s Move In the return type of a call of `mlVec' In the first argument of `M.unsafeRead', namely `(mlVec ml)' which really doesn't make sense, as the package primitive defines the instance: instance PrimMonad (ST s) where type PrimState (ST s) = s primitive = ST internal (ST p) = p Should I do the structure agnostic of that s-state? (forall s. ...) This seems really unintuitive to me... Anybody some hint? Thanks, Nicu

3 4

link to section heading in Haddock
by Edward Amsden 09 Jun '12

09 Jun '12

Hi all After glancing through the haddock documentation and some googling, I can't tell if there's a supported way to link to a section heading in haddock documentation. Is there? Thanks, Ed

2 1