- Glasgow-haskell-users

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

Deadlock with Repa
by Jean-Marie Gaillourdet 29 Jul '10

29 Jul '10

Hi, I've been trying to use repa and stumbled into rather strange behavior of my program. Sometimes, there seems to be a deadlock at other times it seems there is a livelock. Now, I've managed to prepare a version which consistently generates the following output: $ ./MDim MDim: thread blocked indefinitely in an MVar operation $ But I don't use any MVar directly. And the only used library which is not part of ghc are repa and repa-algorithms. To state it clearly I don't use any MVars, par, pseq, forkIO nor any other parallelism or cuncurrency functionality. The only thing my program uses is repa which is supposed to use some kind of parallelism as far as the documentation says. So I am wondering whether this is a problem with my code or with repa or with ghc. The same behaviour occurs with ghc-6.12.1 and ghc-6.13.20100726. This is on MacOSX 10.6.4. In order to reproduce take the attached file and compile it with: $ ghc --make -package dph-prim-par MDim.hs -main-is MDim -fforce-recomp [1 of 1] Compiling MDim ( MDim.hs, MDim.o ) Linking MDim ... $ ./MDim MDim: thread blocked indefinitely in an MVar operation $ I haven't been able to make the program smaller without removing the blockage. But, essentially it's just pure number crunching you can ignore. I'd be really happy if anyone could give me a hint how to debug this, or whether I am able to do anything about it, at all. Best regards, Jean-Marie -- Dipl.-Inf. Jean-Marie Gaillourdet Software Technology Group University of Kaiserslautern, Department of Computer Science Gebäude 32, Raum 406 Gottlieb-Daimler-Str. D-67653 Kaiserslautern Tel: 06 31 - 205 - 32 72 Fax: 06 31 - 205 - 34 20

2 1

SPECIALIZE function for type defined elsewhere
by Sebastian Fischer 28 Jul '10

28 Jul '10

Dear GHC experts, say I have module A where class C a where ... f :: C a => String -> a module B where import A data T = ... instance C T where ... g :: String -> SomeOtherType g s = doSomethingWith (f s) Is it possible to SPECIALIZE `f` for the type `T`? If I put the pragma {-# SPECIALIZE f :: String -> T #-} in module A, GHC complains that `T` is not in scope. If I put it in module B GHC complains that there is no accompanying binding for `f`. In my case, I don't want to put everything in a single module because I cannot know what other B-like modules people will implement. Are they bound to use `f` unspecialized for their types? Why? Cheers, Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

3 3

Allowing Instances to Unify Types
by Matt Brown 27 Jul '10

27 Jul '10

Hi all, I've been hacking on GHC for a couple months now, experimenting with some different ideas I find interesting. One thing I'm trying to do is allow instance unifs (when there's an unambiguous choice, a question which is simplified in this case by there being only one), and force the required unification. Here's a simple example: {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, UndecidableInstances #-} class Apply a b c | a b -> c where applyInst :: a -> b -> c instance (Monad m) => Apply (a -> m b) (m a) (m b) where applyInst = (=<<) apply :: (Monad m) => (a -> m b) -> (m a) -> (m b) apply = (=<<) ioStr :: IO String ioStr = return "foo" printStr :: String -> IO () printStr = print main = do print `apply` (return "foo") printStr `applyInst` ioStr print `applyInst` (return "bar") -- this fails With my code to use the unif instance enabled, I get Ambiguous type variable errors for "Show a" (from print) and "Monad m" (from return). My question is: in the case of apply (which isn't implemented by a class), how does the typechecker propagate "a ~ String" and "m ~ IO" to the predicates for print and return? If someone (such as myself) had sufficient time and energy to spend trying to achieve similar behavior for applyInst, where might he/I start? Thanks and Regards, -matt

3 4