January 2013 - Haskell-Cafe

Re: [Haskell-cafe] Advice on type families and non-injectivity?
by Simon Peyton-Jones 14 Jan '13

14 Jan '13

| > > {-# LANGUAGE TypeFamilies #-} | > > | > > type family F a | > > | > > foo :: F a | > > foo = undefined | > > | > > bar :: F a | > > bar = foo There is a real difficulty here with type-checking 'bar'. (And that difficulty is why 'foo' is also rejected.) Namely, when typechecking 'bar', we must instantiate foo with an unknown type, say alpha. So now we must find a type 'alpha' such that F a ~ F alpha Certainly alpha=1 is one solution, but there might be others. For example, suppose type instance F [b] = F b Then alpha=[a] would also be a solution. In this particular case any solution will do, but suppose there was an addition constraint (C alpha) arising from the right hand side, where C is a class. Then if we had instance C [b] where ... then the second solution (alpha=[a]) would work, but not the first. This can get arbitrarily complicated, and GHC's type inference does not "search" various solutions; it follows one path. The solution is to provide a way to fix alpha. For example, foo :: a -> F a is fine. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces(a)haskell.org [mailto:glasgow-haskell- | users-bounces(a)haskell.org] On Behalf Of Richard Eisenberg | Sent: 14 January 2013 03:47 | To: Conal Elliott | Cc: glasgow-haskell-users(a)haskell.org; Haskell Cafe | Subject: Re: Advice on type families and non-injectivity? | | Hi Conal, | | I agree that your initial example is a little puzzling, and I'm glad | that the new ambiguity checker prevents both definitions, not just one. | | However, your initial question seems broader than just this example. I | have run into this problem (wanting injective type functions) several | times myself, and have been successful at finding workarounds. But, I | can't think of any unifying principle or solid advice. If you can post | more information about your problem, perhaps I or others can contribute. | | For what it's worth, the desire for injective type functions has been | entered as ticket #6018 in the GHC Trac, but I see you're already on the | cc: list. I believe Simon PJ has given serious thought to implementing | this feature and may have even put in some very basic code toward this | end. | | Richard | | On Jan 13, 2013, at 2:10 PM, Conal Elliott <conal(a)conal.net> wrote: | | > I sometimes run into trouble with lack of injectivity for type | families. I'm trying to understand what's at the heart of these | difficulties and whether I can avoid them. Also, whether some of the | obstacles could be overcome with simple improvements to GHC. | > | > Here's a simple example: | > | > > {-# LANGUAGE TypeFamilies #-} | > > | > > type family F a | > > | > > foo :: F a | > > foo = undefined | > > | > > bar :: F a | > > bar = foo | > | > The error message: | > | > Couldn't match type `F a' with `F a1' | > NB: `F' is a type function, and may not be injective | > In the expression: foo | > In an equation for `bar': bar = foo | > | > A terser (but perhaps subtler) example producing the same error: | > | > > baz :: F a | > > baz = baz | > | > Replacing `a` with a monotype (e.g., `Bool`) eliminates the error. | > | > Does the difficulty here have to do with trying to *infer* the type | and then compare with the given one? Or is there an issue even with type | *checking* in such cases? | > | > Other insights welcome, as well as suggested work-arounds. | > | > I know about (injective) data families but don't want to lose the | convenience of type synonym families. | > | > Thanks, -- Conal | > | > _______________________________________________ | > Glasgow-haskell-users mailing list | > Glasgow-haskell-users(a)haskell.org | > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users | | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users(a)haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

2 2

Advice on type families and non-injectivity?
by Conal Elliott 14 Jan '13

14 Jan '13

I sometimes run into trouble with lack of injectivity for type families. I'm trying to understand what's at the heart of these difficulties and whether I can avoid them. Also, whether some of the obstacles could be overcome with simple improvements to GHC. Here's a simple example: > {-# LANGUAGE TypeFamilies #-} > > type family F a > > foo :: F a > foo = undefined > > bar :: F a > bar = foo The error message: Couldn't match type `F a' with `F a1' NB: `F' is a type function, and may not be injective In the expression: foo In an equation for `bar': bar = foo A terser (but perhaps subtler) example producing the same error: > baz :: F a > baz = baz Replacing `a` with a monotype (e.g., `Bool`) eliminates the error. Does the difficulty here have to do with trying to *infer* the type and then compare with the given one? Or is there an issue even with type *checking* in such cases? Other insights welcome, as well as suggested work-arounds. I know about (injective) data families but don't want to lose the convenience of type synonym families. Thanks, -- Conal

4 6

using/building ghc head?
by Johannes Waldmann 14 Jan '13

14 Jan '13

Hi. I wanted to do some experiments with GHC Head but * I cannot use the snapshot bindist: ./configure --prefix=/opt checking for path to top of build tree... ./configure: line 2138: utils/ghc-pwd/dist-install/build/tmp/ghc-pwd-bindist: No such file or directory * I cannot compile snapshot from source (with ghc-7.6.1) utils/haddock/src/Haddock/Convert.hs:201:42: Not in scope: data constructor `HsBang' this is for ghc-7.7.20121213 (date Dec 21), which is the latest snapshot according to http://www.haskell.org/ghc/dist/current/dist/ what am I missing? - J.W.

2 1

How to properly optimize MArray functions for speed?
by Petr P 14 Jan '13

14 Jan '13

Dear Haskellers, I'm working on a sorting library for MArrays. Speed is important, so I want to optimize it as much as possible. Currently, I simply INLINE the sorting function. This speeds up the code more than 10 times. However this can easily explode code size if the function is used in several places. The only other alternative seems to SPECIALIZE the function for all instances of MArray. This also enlarges the resulting code, but only by a constant factor, not depending on how many times the function is used. The question is, is it possible that new instanes of MArray appear? Or is MArray so special and bound to GHC's internals so that I can be sure that no new instances can be defined by some other module? Thanks for help, Petr Pudlak

1 0

Repa: traverse delayed array multiple times
by Andrey Yankin 14 Jan '13

14 Jan '13

Greetings to all! Currently I'm trying to do physical simulations using finite difference method. To accomplish this I need to repeat some manipulations on 2-dimensional grid several thousands or millions times, you know. Is it possible to do using repa? I wrote this rough sketch that shows what I am into. Apparently, program is severely slow. I think reason is: "Every time an element is requested from a delayed array it is calculated anew, which means that delayed arrays are inefficient when the data is needed multiple times" (http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Repa_Tutorial) I started diving into Guiding Parallel Array Fusion with Indexed Types<http://www.cse.unsw.edu.au/%7Ebenl/papers/guiding/guiding-Haskell2012-sub.p…>mentioned there. Is it a right place to find any answer to my question? To summarize, I want to apply my function to Array several thousand times as fast as possible (using multi-threading and GPGPU). It seems I need a lot of memory and throughput. Do I have to call iterate only once at a time or in some kind of batches. What are my possibilities? Thanks in advance! Example program: import System.Environment import Data.Array.Repa as Repa h = 50 w = 50 grid = fromListUnboxed (Z :. h :. w) $ take (h * w) [1, 1..] main = do args <- getArgs let n = read $ head args g <- computeP $ accumulate n grid :: IO (Array U DIM2 Int) putStrLn "Ok" accumulate :: Int -> Array U DIM2 Int -> Array D DIM2 Int accumulate n g = repaIterate step n $ delay g step :: (DIM2 -> Int) -> DIM2 -> Int step f (Z :. i :. j) = center + right + left + top + bottom where left = f' j (i - 1) center = f' j i right = f' j (i + 1) top = f' (j + 1) i bottom = f' (j - 1) i f' j i = if j<0 || i<0 || i>=h || j>=w then 0 else f (Z :. j :. i) repaIterate :: ((DIM2 -> Int) -> DIM2 -> Int) -> Int -> Array D DIM2 Int -> Array D DIM2 Int repaIterate f n = (!! n) . iterate (\array -> traverse array id f) Compilation: ghc -O2 -threaded -rtsopts --make repatest.hs time output: ./repatest 3 +RTS -N2 -H 0,02s user 0,02s system 109% cpu 0,033 total ./repatest 4 +RTS -N2 -H 0,09s user 0,02s system 126% cpu 0,089 total ./repatest 5 +RTS -N2 -H 0,30s user 0,02s system 155% cpu 0,200 total ./repatest 6 +RTS -N2 -H 1,16s user 0,06s system 185% cpu 0,663 total ./repatest 7 +RTS -N2 -H 5,63s user 0,24s system 191% cpu 3,071 total ./repatest 8 +RTS -N2 -H 27,72s user 0,89s system 191% cpu 14,960 total ./repatest 8 +RTS -N1 -H 26,23s user 0,19s system 100% cpu 26,388 total

2 2

Where is the "convergence point" between Category Theory and Haskell?
by Alfredo Di Napoli 14 Jan '13

14 Jan '13

Morning Cafe, I'm planning to do a series of write-ups about Category Theory, to publish them on the company's blog I'm currently employed. I'm not a CT expert, but since the best way to learn something is to explain it to others, I want to take a shot :) In my mind I will structure the posts following Awodey's book, but I'm wondering how can I make my posts a little more "real world". I always read about the "Hask category", which seems to be the "bootstrap" of the whole logic behind Haskell. Can you please give my materials/papers/links/blogs to the Hask category and briefly explain me how it relates to Category Theory and Haskell itself? I hope my question is clear enough, in case is not, I'll restate :P Cheers, A.

5 7

Announce: Leksah 0.13.1 (a bit experimental)
by Hamish Mackenzie 14 Jan '13

14 Jan '13

This has mostly bug fixes, GHC 7.4.2, GHC 7.6.1 and Gtk3 support. I have not uploaded it to Hackage as it uses Gtk2Hs patches that are not in Hackage. New features include "View->Dark" (OS X only) and "View->Fullscreen". OS X (using Gtk3) ----------------- Choose the version that matches your installed GHC http://leksah.org/packages/leksah-0.13.1.0-ghc-7.0.3.dmg http://leksah.org/packages/leksah-0.13.1.0-ghc-7.0.4.dmg http://leksah.org/packages/leksah-0.13.1.0-ghc-7.4.1.dmg http://leksah.org/packages/leksah-0.13.1.0-ghc-7.4.2.dmg http://leksah.org/packages/leksah-0.13.1.0-ghc-7.6.1.dmg (probable needs OS X 10.7) Windows (still Gtk2) -------------------- Choose the version that matches your installed GHC http://leksah.org/packages/leksah-0.13.1.0-ghc-7.0.3.exe http://leksah.org/packages/leksah-0.13.1.0-ghc-7.0.4.exe http://leksah.org/packages/leksah-0.13.1.0-ghc-7.4.1.exe http://leksah.org/packages/leksah-0.13.1.0-ghc-7.4.2.exe Linux ----- Follow the steps in the .travis.yml file... https://github.com/leksah/leksah/blob/master/.travis.yml Should go something like this... https://travis-ci.org/leksah/leksah

4 6

cabal sdist warns about optimization levels
by Petr P 13 Jan '13

13 Jan '13

Hi all, I'm working on a library for fast sorting of MArrays. The library is primarily about speed, so I added ghc-options: -O2 to the cabal file. Now cabal sdist complains with: 'ghc-options: -O2' is rarely needed. Check that it is giving a real benefit and not just imposing longer compile times on your users. I wonder: (1) Is there a way how to disable the warning? As the main aim of the library is speed, I believe -O2 is appropriate here. And since the code is quite short, I'm quite sure the increased compile time won't be noticeable. (2) Why does cabal complain about it at the first place? I found a reference saying the warning is adequate: https://github.com/haskell/cabal/issues/808 but not saying why. Maybe for complex programs -O2 prolongs compile time too much, but libraries are usually compiled once and used many times, so using -O2 for them seems reasonable in many cases. Thanks for help, Petr Pudlak

3 2

Re: [Haskell-cafe] Advice on type families and non-injectivity?
by Conal Elliott 13 Jan '13

13 Jan '13

Hi Christian, Given "bar :: Bool", I can't see how one could go from "Bool" to "F a = > Bool" and determine "a" uniquely. > The same question applies to "foo :: Bool", right? Yet no error message there. Regards, - Conal On Sun, Jan 13, 2013 at 11:36 AM, Christian Höner zu Siederdissen < choener(a)tbi.univie.ac.at> wrote: > Hi, > > How would you infer "a" from "F a"? Given "bar :: Bool", I can't see how > one could go from "Bool" to "F a = Bool" and determine "a" uniquely. > > My question is not completely retorical, if there is an answer I would > like to know it :-) > > Gruss, > Christian > > > * Conal Elliott <conal(a)conal.net> [13.01.2013 20:13]: > > I sometimes run into trouble with lack of injectivity for type > families. > > I'm trying to understand what's at the heart of these difficulties and > > whether I can avoid them. Also, whether some of the obstacles could be > > overcome with simple improvements to GHC. > > > > Here's a simple example: > > > > > {-# LANGUAGE TypeFamilies #-} > > > > > > type family F a > > > > > > foo :: F a > > > foo = undefined > > > > > > bar :: F a > > > bar = foo > > > > The error message: > > > > Couldn't match type `F a' with `F a1' > > NB: `F' is a type function, and may not be injective > > In the expression: foo > > In an equation for `bar': bar = foo > > > > A terser (but perhaps subtler) example producing the same error: > > > > > baz :: F a > > > baz = baz > > > > Replacing `a` with a monotype (e.g., `Bool`) eliminates the error. > > > > Does the difficulty here have to do with trying to *infer* the type > and > > then compare with the given one? Or is there an issue even with type > > *checking* in such cases? > > > > Other insights welcome, as well as suggested work-arounds. > > > > I know about (injective) data families but don't want to lose the > > convenience of type synonym families. > > > > Thanks, -- Conal > > > _______________________________________________ > > Glasgow-haskell-users mailing list > > Glasgow-haskell-users(a)haskell.org > > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users > >

1 0

Generating random arguments for a function
by satvik chauhan 13 Jan '13

13 Jan '13

I am trying to use quickcheck to generate random arguments of a given function (assuming all its types have Arbitrary instance and Show instance) along with the evaluation of the function at those arguments. Suppose I have a function add :: Int -> Int -> Int add a b = a+b Then I assume a behavior like > randomEvaluate add (["1","3"],"4") where 1 and 3 are random values generated for `Int` and 4 is `f 1 3`. I have asked this on SO<http://stackoverflow.com/questions/14294802/evaluating-function-at-random-a…> but am not fully satisfied with the answers. -Satvik

5 6