April 2009 - Haskell-Cafe

Code Golf
by Sebastian Fischer 20 Apr '09

20 Apr '09

Fancy some Codegolf? I wrote the following function for list diagonalization: > diag l = foldr (.) id ((sel l . flip sel) ((:[]).(:))) [] > where > sel = foldr (\a b c -> id : mrg (a c) (b c)) (const []) . map (flip id) > > mrg [] ys = ys > mrg xs [] = xs > mrg (x:xs) (y:ys) = (x.y) : mrg xs ys Self explanatory, isn't it? Here is a test case: *Main> take 10 $ diag [[ (m,n) | n <- [1..]] | m <- [1..]] [(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),(2,3),(3,2),(4,1)] I was trying to golf it down [^1] but my brain explodes. If you succeed in reducing keystrokes, I'd be happy to know! Cheers, Sebastian [^1]: http://codegolf.com/

8 16

Re: [Haskell-cafe] ANNOUNCE: Utrecht Haskell Compiler (UHC) -- first release
by Niemeijer, R.A. 20 Apr '09

20 Apr '09

> data EShow = forall a. Show a => EShow a > > data E t = forall a. E (a->t) a > > smallPrint_ t = concatMap (\f-> f t) [show . foo, show . bar, show . baz] Yeah, I am aware of these solutions, but like Dan says: > but first-class existentials are still desirable because introducing a new > type for every existential is annoying. It's comparable to having to write a > new class for every combination of argument and result types to mimic first > class functions in Java (aside from first class functions being more > ubiquitous in their usefulness, although perhaps it only appears that way > because we don't have easy use of existential types). I've personally always looked at the extra data type or repeated functions as ugly hacks around the fact that GHC doesn't have real existential typing. Since Haskell is otherwise virtually free of ugly hacks (at least at the level I work at, which doesn't require things like unsafePerformIO and unboxed arrays) this has always annoyed me a bit. So I figured that since we now have a working implementation it would be worth a shot to ask if this language wart can be removed from GHC.

1 0

Re: [Haskell-cafe] General function to count list elements?
by michael rice 20 Apr '09

20 Apr '09

I know functions can be compared in Scheme Welcome to DrScheme, version 4.1 [3m]. Language: Swindle; memory limit: 128 megabytes. > (equal? equal? equal?) #t > but apparently not in Haskell [michael@localhost ~]$ ghci GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> (==) (==) (==) <interactive>:1:0: No instance for (Eq (a -> a -> Bool)) arising from a use of `==' at <interactive>:1:0-13 Possible fix: add an instance declaration for (Eq (a -> a -> Bool)) In the expression: (==) (==) (==) In the definition of `it': it = (==) (==) (==) Prelude> though I'm new at Haskell and may not be posing the question properly. I would think a language with 1st-class support for functions would certainly include comparing them. To compare two functions in C, I would compare their machine addresses. Michael --- On Sat, 4/18/09, Eugene Kirpichov <ekirpichov(a)gmail.com> wrote: From: Eugene Kirpichov <ekirpichov(a)gmail.com> Subject: Re: [Haskell-cafe] General function to count list elements? To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Saturday, April 18, 2009, 11:39 AM Could you then provide an example of two functions that *are* equal, or, even better, a definition of equality for arbitrary functions? Since Haskell may be compiled into C, this must be a definition that is implementable in C. 2009/4/18 michael rice <nowgate(a)yahoo.com>: > Though I haven't tried it out, it's trying to use my function to count > functions. > > The first argument is the identity function. > > The second argument is a list of a different form of the identity function. > > Though the two identity functions, given the same input, would produce the > same output, I doubt they would be equal. > > So my guess at an answer would be zero. > > Michael > > --- On Sat, 4/18/09, Eugene Kirpichov <ekirpichov(a)gmail.com> wrote: > > From: Eugene Kirpichov <ekirpichov(a)gmail.com> > Subject: Re: [Haskell-cafe] General function to count list elements? > To: "michael rice" <nowgate(a)yahoo.com> > Cc: haskell-cafe(a)haskell.org > Date: Saturday, April 18, 2009, 11:03 AM > > What should > > count (\x -> x) (replicate 10 (\y -> if 1==1 then y else undefined)) > > return? > > 2009/4/18 michael rice <nowgate(a)yahoo.com>: >> Is there a general function to count list elements. I'm trying this >> >> count :: a -> [a] -> Int >> count x ys = length (filter (== x) ys) >> >> with this error upon loading >> >> ============= >> >> [michael@localhost ~]$ ghci count >> GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help >> Loading package ghc-prim ... linking ... done. >> Loading package integer ... linking ... done. >> Loading package base ... linking ... done. >> [1 of 1] Compiling Main ( count.hs, interpreted ) >> >> count.hs:2:29: >> Could not deduce (Eq a) from the context () >> arising from a use of `==' at count.hs:2:29-32 >> Possible fix: >> add (Eq a) to the context of the type signature for `count' >> In the first argument of `filter', namely `(== x)' >> In the first argument of `length', namely `(filter (== x) ys)' >> In the expression: length (filter (== x) ys) >> Failed, modules loaded: none. >> Prelude> >> >> ============= >> >> Not sure what it's trying to tell me other than I need an (Eq a) >> somewhere. >> >> Michael >> >> >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >> > > > > -- > Eugene Kirpichov > Web IR developer, market.yandex.ru > > -- Eugene Kirpichov Web IR developer, market.yandex.ru

5 5

Re: [Haskell-cafe] ANNOUNCE: Utrecht Haskell Compiler (UHC) -- first release
by Niemeijer, R.A. 20 Apr '09

20 Apr '09

> * Experimental language extensions, some of which have not been > implemented before. Does anybody know if there are any plans to incorporate some of these extensions into GHC - specifically the existential typing ? I would love to be able to use existential typing without having to give up the robustness of GHC.

5 7

Re: Matrices
by Patrick Perry 20 Apr '09

20 Apr '09

Hi Cetin, This is probably the easiest way: > (m - es)^2/es listMatrix (2,2) [0.6163270413689804,0.600918865334756,0.33217626255600896,0.3238718559921087 ] This will create 2 temporary arrays. Alternatively, > let res = listMatrix (shape m) [ (o-e)^2 / e | o <- colElems m | e <- colElems es ] where colElems = concatMap elems . cols > res listMatrix (2,2) [0.6163270413689804,0.600918865334756,0.33217626255600896,0.3238718559921087 ] In a later version of the library, "colElems" will probably be built- in. This version has the disadvantage that it doesn't use BLAS calls. If you *really* want to get tricky and eliminate temporary arrays: > runSTMatrix $ do res <- newCopyMatrix m subMatrix res es modifyWith (^2) res divMatrix res es return res Now, to get the sum: > sumAbs $ vectorFromMatrix res 1.8732940252518542 or > sum $ elems res 1.8732940252518542 The first version will usually be more efficient, since it calls the BLAS1 function "dasum". Patrick

1 0

Looking for the fastest Haskell primes algorithm
by Niemeijer, R.A. 20 Apr '09

20 Apr '09

Today I happened to need a large list of prime numbers. Obviously this is a well-known problem, so I figured there would be something on Hackage that I could use. Surprisingly, there isn't, or if there is it's not easy to find. Searching for prime or primes on Hackage reveals nothing. Searching for primes on Hayoo gives Codec.Encryption.RSA.NumberTheory, but that uses the inefficient one-liner implementation. The HaskellWiki article on primes (http://www.haskell.org/haskellwiki/Prime_numbers) has a number of implementations, but the faster they get, the longer and uglier they become. Since it's such a common problem I'd say it would be a good idea to add a package to Hackage that exports primes :: [Integer] and hides the ugly implementation details. Data.Numbers.Primes seems a logical choice for the namespace, but I'm open to suggestions. The trick then is to find the most efficient implementation of primes. The Haskell wiki article mentions ONeillPrimes.hs as one of the fastest ones, but maybe there's a faster version. So my question is: does anybody know what the fastest Haskell algorithm for generating primes is?

14 14

Fwd: [Haskell-cafe] General function to count list elements?
by Alberto G. Corona 19 Apr '09

19 Apr '09

here goes a test of pointer equality (valid for functions too): samepointer :: a -> a -> IO Bool samepointer f1 f2 = do p1<- varHash f1 p2<- varHash f2 return $ p1 == p2 where varHash x= do sn <- makeStableName x return $ hashStableName sn 2009/4/18 <nowgate(a)yahoo.com>: > Hi John, > > Yes, I see now what the hullabaloo was about. > > I've only been hacking Haskell for a few weeks, so I'm still seeing the > "forest" rather than the "trees". But I'm coming along. > > Thanks. > > Michael > > --- On Sat, 4/18/09, John Dorsey <haskell(a)colquitt.org> wrote: > > From: John Dorsey <haskell(a)colquitt.org> > Subject: Re: [Haskell-cafe] General function to count list elements? > To: "michael rice" <nowgate(a)yahoo.com> > Cc: haskell-cafe(a)haskell.org > Date: Saturday, April 18, 2009, 2:36 PM > > Michael, > >> I had a count function that worked fine for an enum type, but thought >> why not go polymorphic with it. So I changed it and got the error I >> originally inquired about. > > For variety, I'll go a slightly different direction. > > If you generalize count to use any predicate, instead of always > equality... > > gcount :: (a -> a -> Bool) -> a -> [a] -> Int > gcount pred x0 xs = length (filter (pred x0) xs) > > count = gcount (==) > > This will work with any type that you can write a predicate for with the > type (a -> a -> Bool). I can even use this with functions, if I'm > careful. > > ghci> gcount (\f g -> True) (*2) [id,(const 1),(*3)] > 3 > ghci> gcount (\f g -> f 1 == g 1) (^2) [id,(const 1),(*3)] > 2 > > By the way, do you see why everyone's bothing you about comparing > functions? The type you gave count, which didn't have an Eq constraint, > was an assertion that you could compare two values of *any* type. If > there's a type that's not comparable, then count's type was wrong. > Functions are the canonical example of an incomparable type. > > When you're bored some time, read a bit about the Curry-Howard > correspondence. It's interesting, even if (like me) you don't grok all > of its implications. > > Regards, > John > > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

1 0

RE: [Haskell-cafe] ANNOUNCE: Utrecht Haskell Compiler (UHC) -- first release
by Niemeijer, R.A. 19 Apr '09

19 Apr '09

If only it were that easy. Sadly, it's not. Let's look at the following example: data Test = Test { foo :: Int, bar :: Char, baz :: Bool } smallPrint t = concatMap (\f -> show $ f t) [foo, bar, baz] In this code the list [foo, bar, baz] should have the type [exists a. Show a => Test -> a]. If we explicitly specify the type, replacing the exists with a forall, then GHC complains about not being able to match Int, Char and Bool against type a. Forall is not the same as exists and GHC only implements the former. ________________________________________ From: Bulat Ziganshin [bulat.ziganshin(a)gmail.com] Sent: 19 April 2009 22:07 To: Niemeijer, R.A. Cc: haskell-cafe(a)haskell.org Subject: Re[2]: [Haskell-cafe] ANNOUNCE: Utrecht Haskell Compiler (UHC) -- first release Hello R.A., Sunday, April 19, 2009, 11:46:53 PM, you wrote: > Does anybody know if there are any plans to incorporate some of > these extensions into GHC - specifically the existential typing ? it is already here, but you should use "forall" keyword instead odf "exists" -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 1

Re: [Haskell-cafe] ANNOUNCE: Utrecht Haskell Compiler (UHC) -- first release
by Daniel Fischer 19 Apr '09

19 Apr '09

Am Sonntag 19 April 2009 13:09:17 schrieb Thomas Davie: > >> I don't understand what makes user installs more convenient. > >> Certainly, > >> my preference would be for global all the time I expect something > >> that > >> says it's going to "install" something to install it onto my > >> computer, > >> like any other installation program does. What is it that makes user > >> installs more convenient in this situation? > > > > You don't need 'sudo' access for user installs. This means that 'cabal > > install' works out of the box on every system, without needing > > admin/root privs (esp. important for students). > > But students will be used to needing to configure this in every > other installation system out there they need to tell it to install in > their user directory. Personally I find it more convenient to have > the "install" program do what it says it does! Install it! But it does install it, only not where you want it. Just for the record, I (no student, my own computer, sole user) prefer user-installs and cabal's default behaviour. Makes it so much easier to get rid of things I don't want anymore without any fear of buggering my system because something depends on it. > > This would save confusion about old tools that do things globally, and > not confuse students, because they're all already used to giving extra > flags to make install not install things system wide. Yes, it is bad that the runhaskell Setup interface has a different default. But, as Duncan said, too late to change it now. > > Bob

3 4

Re: [Haskell] Helpful libraries to implement a board game?
by Conrad Meyer 19 Apr '09

19 Apr '09

On Sunday 19 April 2009 01:39:40 pm Frank Rosemeier wrote: > Dear Haskellers, > > I would like to implement a board game for a single player in Haskell. > The pieces may be moved one step in any direction if there is no > piece next to it, > and the goal is to rearrange the pieces to their home positions. > The Haskell program should find an optimal solution (with minimal > number of moves). > > Can anybody recommend some helpful libraries for this task? > Any hints are very welcome! > > > Frank Rosemeier (This should probably be on haskell-cafe, so I'm moving it there, CC-ing the author.) Hi, If you're interested in gametree search (i.e. game AI), which it sounds like you are, then the game-tree library on Hackage may interest you[0]. [0]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/game-tree Regards, -- Conrad Meyer <konrad(a)tylerc.org>

1 0