August 2010 - Glasgow-haskell-users

ANN: Data.Array.Accelerate 0.8.0.0 — an EDSL for accelerated array computations
by Manuel M T Chakravarty 22 Aug '10

22 Aug '10

Data.Array.Accelerate defines an embedded language of array computations for high-performance computing. Computations on multi-dimensional, regular arrays are expressed in the form of parameterised collective operations (such as maps, reductions, and permutations). Version 0.8.0.0 of Accelerate includes a mostly feature-complete backend generating code for NVIDIA's CUDA language for general-purpose GPU computing. More on this release is at http://justtesting.org/second-beta-release-for-the-cuda-backend-of-a On Hackage: http://hackage.haskell.org/package/accelerate If you are keen on Haskell on GPUs, give this a spin! Manuel

1 0

Possible bug with GADTs?
by Dan Knapp 18 Aug '10

18 Aug '10

Below, please find a snippet from a program I'm working on, and the error it produces. I was told in #haskell that this was "pretty suspect" and could conceivably be a ghc bug. So I'm reporting it here. I'd also be grateful for workarounds. This is on ghc 6.12.1.20100203, but if people can't reproduce it I'll install a newer one; I'm just not eager to do that because of course it means rebuilding quite a lot of things. {-# LANGUAGE GADTs #-} module Foo where data TemplateValue t where TemplateList :: [a] -> TemplateValue [a] instance (Eq a) => Eq (TemplateValue a) where (==) (TemplateList a) (TemplateList b) = (==) a b Foo.hs:7:45: Could not deduce (Eq a1) from the context (a ~ [a2]) arising from a use of `==' at Foo.hs:7:45-52 Possible fix: add (Eq a1) to the context of the constructor `TemplateList' In the expression: (==) a b In the definition of `==': == (TemplateList a) (TemplateList b) = (==) a b In the instance declaration for `Eq (TemplateValue a)' -- Dan Knapp "An infallible method of conciliating a tiger is to allow oneself to be devoured." (Konrad Adenauer)

5 6

Re: Surprising strictness properties of pre-order fold over a Data.Map
by Johan Tibell 18 Aug '10

18 Aug '10

On Wed, Aug 18, 2010 at 4:38 PM, Lennart Augustsson < lennart.augustsson(a)gmail.com> wrote: > You don't know that f is strict in its first argument so you cannot > deduce that go is strict in z in the first case. > I'm not sure I understand. f :: Int -> Int -> Int -> Int f = \x y z -> x + y + z in this particular case so it's strict in all its parameters since + is strict (for Ints). f is inlined into go so it should be possible to deduce that go is indeed strict. As I mentioned to Ian you get the same result if you inline f manually. Cheers, Johan

1 0

Surprising strictness properties of pre-order fold over a Data.Map
by Johan Tibell 18 Aug '10

18 Aug '10

Hi, I was adding a strict pre-order fold to the Data.Map module and I ran into this slightly surprising behavior. Modeled on foldl' for lists I defined foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b foldlWithKey' f z0 m = go z0 m where go z Tip = z go z (Bin _ kx x l r) = let x' = f (go z l) kx x in x' `seq` go x' r {-# INLINE foldlWithKey' #-} and, in a separate module, I defined this test module Test (test) where import qualified Data.Map as M test :: M.Map Int Int -> Int test m = M.foldlWithKey' (\n k v -> n + k + v) 0 m which generates this core: test1 :: Int test1 = I# 0 test_go2 :: Int -> Data.Map.Map Int Int -> Int test_go2 = \ (z_ani :: Int) (ds_anj :: Data.Map.Map Int Int) -> case ds_anj of _ { Data.Map.Tip -> z_ani; Data.Map.Bin _ kx_anp x_anq l_anr r_ans -> case test_go2 z_ani l_anr of _ { I# x1_ao5 -> case kx_anp of _ { I# y_ao9 -> case x_anq of _ { I# y1_Xot -> test_go2 (I# (+# (+# x1_ao5 y_ao9) y1_Xot)) r_ans } } } } test :: Data.Map.Map Int Int -> Int test = \ (m_ajo :: Data.Map.Map Int Int) -> test_go2 test1 m_ajo Note how the accumulator 'z' is not unboxed in the loop. I don't quite understand why that is. I do know I can get the core that I want by defining foldlWithKey2' :: (b -> k -> a -> b) -> b -> Map k a -> b foldlWithKey2' f z0 m = go z0 m where go z _ | z `seq` False = undefined go z Tip = z go z (Bin _ kx x l r) = go (f (go z l) kx x) r {-# INLINE foldlWithKey2' #-} and module Test (test2) where import qualified Data.Map as M test2 :: M.Map Int Int -> Int test2 m = M.foldlWithKey2' (\n k v -> n + k + v) 0 m you get this core: test2_$s$wgo2 :: Data.Map.Map Int Int -> Int# -> Int# test2_$s$wgo2 = \ (sc_soS :: Data.Map.Map Int Int) (sc1_soT :: Int#) -> case sc_soS of _ { Data.Map.Tip -> sc1_soT; Data.Map.Bin _ kx_anK x_anL l_anM r_anN -> case test2_$s$wgo2 l_anM sc1_soT of ww_sou { __DEFAULT -> case kx_anK of _ { I# y_ao9 -> case x_anL of _ { I# y1_Xow -> test2_$s$wgo2 r_anN (+# (+# ww_sou y_ao9) y1_Xow) } } } } $wtest2 :: Data.Map.Map Int Int -> Int# $wtest2 = \ (w_sox :: Data.Map.Map Int Int) -> test2_$s$wgo2 w_sox 0 test2 :: Data.Map.Map Int Int -> Int test2 = __inline_me (\ (w_sox :: Data.Map.Map Int Int) -> case $wtest2 w_sox of ww_soA { __DEFAULT -> I# ww_soA }) Note that the accumulator is now unboxed. Could someone please explain the difference. I would like to be able to to understand when I would get the former or the latter by looking at the Haskell source. Cheers, Johan

2 2

Template Haskell reification of instances
by Simon Peyton-Jones 13 Aug '10

13 Aug '10

Dear TH users In Template Haskell, it's not currently possible to say "give me all the instances of this class"; it's a long-standing feature request. Sam Anklesaria has come up with a design and implemented it. Before committing to it, I want to check that other Template Haskell users are happy with the design. You can find the details here: http://hackage.haskell.org/trac/ghc/ticket/1835 But a summary of the design appears below. If you have a stake in Template Haskell, pls RSVP by adding a comment to the ticket. Thanks Simon ================ Proposed design * Extending the Quasi monad to have class (Monad m, Functor m) => Quasi m where ... qReify :: Name -> m Info qIsClassInstance :: Name -> [Type] -> m Bool isClassInstance :: Name -> [Type] -> Q Bool isClassInstance n ts = Q (qIsClassInstance n ts) * Extending the info you get back when reifying a Class, by adding its instances: data Dec = ... | ClassI Dec [([TyVarBndr],Cxt,[Type])] Some random thoughts * In principle, I suppose that isClassInstance isn't really necessary: you could reify the class and search the list yourself. But I can see that it's convenient. * Currently isClassInstance returns True if any instances match, even if they overlap etc. Might you want to know more?

1 0

Using associated data types to create unpacked data structures
by Johan Tibell 13 Aug '10

13 Aug '10

Hi all, Inspired by the generic maps example at http://www.haskell.org/haskellwiki/GHC/Indexed_types I tried to use associated data types to create a generic finite map that unpacks both the key and value into the leaf data constructor. This makes functions such as lookup faster as the key can be accessed directly instead than via an indirection. It also makes the data structure more space efficient (4 words less per key/value pair for weight balanced trees), which makes it possible to fit more data in main memory (and cache). Memory overhead is important when working with "Big Data" processing, where fitting as much data in memory as possible is important. Working with big data sets is something done daily at companies like Google, Microsoft, Yahoo, Twitter, Facebook, etc. We can achieve the above goals using an associated data type like so: {-# LANGUAGE MultiParamTypeClasses, TypeFamilies #-} module Ex where class Unbox k v where data Map k v :: * empty :: Map k v lookup :: k -> Map k v -> Maybe v insert :: k -> v -> Map k v -> Map k v and an instance instance Unbox Int Double where data Map Int Double = TipIntDouble | BinIntDouble {-# UNPACK #-} !Size {-# UNPACK #-} !Int {-# UNPACK #-} !Double !(Map Int Double) !(Map Int Double) -- implementation elided empty = undefined lookup k m = undefined insert k v m = undefined type Size = Int However, if we try to apply this method to large programs we run into problems: we need to defined instances for a large number of combinations of keys/values. We could generate a large number of instances, hoping that these will be enough for most users' needs, using Template Haskell or CPP. However, the potential number of instances is very large, about a hundred if you consider only Prelude types and tens of thousands if you include tuples. We cannot add instances for types not defined in base without adding a dependency on all libraries which data types we want to add instances for. Since we cannot define all instances up-front we'll have to rely on the user to create instances for the combinations she needs. This is tedious work for the user; most of the time the instance is an exact copy of the above instance for Int/Double, modulo renaming of the type arguments and the constructor names. Unfortunately our problems don't end here. If we assume for a second that the user writes the necessary boilerplate (perhaps using a Template Haskell function that generates it) there are still more problems ahead. It's quite likely that two different libraries wants an instance for the same types, and each declare one locally. However, now the poor user can't use both libraries as there are conflicting instances (or can she using some extension?) and imports always bring in instances. This problem exists for type classes in general but we only use ten or so type classes in most Haskell programs (e.g Functor, Monad, Eq, Ord, and Show) so it doesn't seem to be a big problem so far. What to do? It seems that associated data types might not be right tool for this problem. Could it be extended to work well for this use case? Can it be made to *scale* to large programs. Here's an idea: allow default implementations of associated data types, just like for methods class Unbox k v where data Map k v :: * empty :: Map k v lookup :: k -> Map k v -> Maybe v insert :: k -> v -> Map k v -> Map k v data Map Int Double = Tip | Bin {-# UNPACK #-} !Size {-# UNPACK #-} !k {-# UNPACK #-} !v !(Map k v) !(Map k v) -- implementation elided empty = undefined lookup k m = undefined insert k v m = undefined and export the definition in the interface file. This would allow instantiation of the type class without boilerplate instance Unbox Int Double -- no "body" The compiler would perhaps have to generate unique names for the constructors for this to work. This is not enough. We still have two problems left: * boilerplate instance declarations (but less so that before), and * instance collisions. Could we automatic create instances whenever the user mentions a type class? For example, if a program mentions f :: Map Int Double -> ... we know we need an instance for Int/Double and if we can't find one we derive one using the default definition. It is all the user needs to do when using the classic containers package. This would completely remove the boilerplate instance declarations. We could still use OverlappingInstances to allow the user to provide more specific instances (with a different implementation), if needed. This is akin to C++ template specialization. The compiler will need to help us with the instance collision problem in that it only generates on instance even if the same type parameters are used with the Map type in several different modules. Summary: While associated data types in theory allows us to create more efficient data structures, the feature doesn't seem to scale to large programs, for this use case. Cheers, Johan

8 19

how to link a minimal executable?
by Greg Fitzgerald 12 Aug '10

12 Aug '10

Is there any documentation or examples available that shows what needs to be linked to get a haskell executable to print "hello world"? Instead of using GHC to link, I'm interested in using gcc, ar, or link directly. For starters, what implements the entry point? $ cat Main.hs main = print "hello world" $ ghc -c Main.hs $ Vs8/VC/bin/link.exe -NOLOGO Main.o LINK : fatal error LNK1561: entry point must be defined I see using ghc -v, it links all sorts of stuff: $ ghc -v Main.hs ... *** Linker: ... -lHSrtsmain -lHShaskell98-1.0.1.1 -lHSrandom-1.0.0.2 -lHStime-1.1.4 -lHSprocess-1.0.1.2 -lHSdirectory-1.0.1.0 -lHSold-time-1.0.0.3 -lHSold-locale-1.0.0.2 -lHSfilepath-1.1.0.3 -lHSWin32-2.2.0.1 -luser32 -lgdi32 -lwinmm -ladvapi32 -lshell32 -lshfolder -lHSbytestring-0.9.1.5 -lHSarray-0.3.0.0 -lHSbase-4.2.0.0 -lwsock32 -luser32 -lshell32 -lHSinteger-simple-0.1.0.0 -lHSghc-prim-0.2.0.0 -lHSrts -lm -lwsock32 -u _ghczmprim_GHCziTypes_Izh_static_info -u _ghczmprim_GHCziTypes_Czh_static_info -u _ghczmprim_GHCziTypes_Fzh_static_info -u _ghczmprim_GHCziTypes_Dzh_static_info -u _base_GHCziPtr_Ptr_static_info -u _base_GHCziWord_Wzh_static_info -u _base_GHCziInt_I8zh_static_info -u _base_GHCziInt_I16zh_static_info -u _base_GHCziInt_I32zh_static_info -u _base_GHCziInt_I64zh_static_info -u _base_GHCziWord_W8zh_static_info -u _base_GHCziWord_W16zh_static_info -u _base_GHCziWord_W32zh_static_info -u _base_GHCziWord_W64zh_static_info -u _base_GHCziStable_StablePtr_static_info -u _ghczmprim_GHCziTypes_Izh_con_info -u _ghczmprim_GHCziTypes_Czh_con_info -u _ghczmprim_GHCziTypes_Fzh_con_info -u _ghczmprim_GHCziTypes_Dzh_con_info -u _base_GHCziPtr_Ptr_con_info -u _base_GHCziPtr_FunPtr_con_info -u _base_GHCziStable_StablePtr_con_info -u _ghczmprim_GHCziBool_False_closure -u _ghczmprim_GHCziBool_True_closure -u _base_GHCziPack_unpackCString_closure -u _base_GHCziIOziException_stackOverflow_closure -u _base_GHCziIOziException_heapOverflow_closure -u _base_ControlziExceptionziBase_nonTermination_closure -u _base_GHCziIOziException_blockedIndefinitelyOnMVar_closure -u _base_GHCziIOziException_blockedIndefinitelyOnSTM_closure -u _base_ControlziExceptionziBase_nestedAtomically_closure -u _base_GHCziWeak_runFinalizzerBatch_closure -u _base_GHCziTopHandler_runIO_closure -u _base_GHCziTopHandler_runNonIO_closure -u _base_GHCziConc_ensureIOManagerIsRunning_closure -u _base_GHCziConc_runSparks_closure -u _base_GHCziConc_runHandlers_closure -lHSffiReading Any insight would be greatly appreciated. Thanks, Greg

3 2

$thisdir for package.conf?
by Greg Fitzgerald 12 Aug '10

12 Aug '10

Is there a way for a package.conf file to contain paths that are relative to the directory containing the .conf file? GHC 6.12.1 chokes on relative paths. I see the problem is solved for GHC's core libraries with the $topdir variable. Is there something like a $thisdir we could use in inplace .conf files? Thanks, Greg

2 1

Re: [Haskell-cafe] Weird behavior with arrow commands
by Jürgen Doser 02 Aug '10

02 Aug '10

El vie, 23-07-2010 a las 23:27 -0400, Ronald Guida escribió: > I am trying to figure out how to use GHC's arrow commands, and I found > some extremely weird behavior. CC'ed to ghc-users, because this may be a ghc bug. > In GHC's manual, there is a description of arrow commands, which I > don't really understand. > http://www.haskell.org/ghc/docs/latest/html/users_guide/arrow-notation.html… > (Primitive Constructs) > > I have two questions: > 1. What are arrow commands supposed to do? > 2. What is this code supposed to do? > > -- start of code -- > > {-# LANGUAGE Arrows #-} > module Main where > > import Control.Arrow > > foo :: (b -> String) -> ((((b, Int), Float), Double) -> String) -> (b -> String) > foo f g b = f b ++ " " ++ g (((b, 8), 1.0), 6.0) > > bar :: (t -> String) -> ((Double, Int) -> String) -> t -> String > bar f g = proc x -> do > (f -< x) `foo` \n m -> g -< (n) > > main = do > putStrLn $ foo show show 17 > putStrLn $ bar show show 17 > putStrLn $ foo show show 42 > putStrLn $ bar show show 42 > > -- end of code -- > > Output from GHCi: > > 17 (((17,8),1.0),6.0) > 17 (6.730326920298707e-306,0) > 42 (((42,8),1.0),6.0) > 42 (6.730326920298707e-306,0) > > Output after compiling with GHC: > > 17 (((17,8),1.0),6.0) > 17 (5.858736684536801e-270,0) > 42 (((42,8),1.0),6.0) > 42 (5.858736684536801e-270,0) > > GHC Version: > The Glorious Glasgow Haskell Compilation System, version 6.12.3 This seems to be a bug in ghc. First, let's fix bar to give the full three arguments (Int, Float, Double) to g: bar f g = proc x -> do (f -< x) `foo` (\n m k -> g -< (n,m,k)) ghc infers the type: bar :: (t -> String) -> ((Double, Float, Int) -> String) -> t -> String and we see that the argument order in the second argument to bar is reversed. But the arguments are still given to bar in the order (Int, Float, Double). For example, the 6.0 in foo is interpreted as an Int and outputs a 0 (the first 32 bits in such a small double are zeros). When one varies the numbers in foo, one can see the effects in bar. Can someone from GHC HQ confirm my understanding, or is this just not supposed to work with multiple arguments? Jürgen

3 2