- Haskell-Cafe - Haskell.org

CPS and the product function
by michael rice 20 Apr '09

20 Apr '09

I've been looking at CPS in Haskell and wondering how many multiplications the product function performs if it encounters a zero somewhere in the input list. Zero? Does anyone know the definition of the product function? Michael

3 2

Re: [Haskell-cafe] CPS and the product function
by michael rice 20 Apr '09

20 Apr '09

Hi Eugene, Clever solution. It didn't come right back so I interrupted it. Guess it would do all those multiplies by zero. Does anyone know how to define it to avoid that? Thanks. Michael --- On Mon, 4/20/09, Eugene Kirpichov <ekirpichov(a)gmail.com> wrote: From: Eugene Kirpichov <ekirpichov(a)gmail.com> Subject: Re: [Haskell-cafe] CPS and the product function To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Monday, April 20, 2009, 9:40 AM Check that by experiment in ghci or by looking at the source: Prelude*> product [0..] Or search "product" at http://holumbus.fh-wedel.de/hayoo/hayoo.html and click on one of the Source links. 2009/4/20 michael rice <nowgate(a)yahoo.com>: > I've been looking at CPS in Haskell and wondering how many multiplications > the product function performs if it encounters a zero somewhere in the input > list. Zero? > > Does anyone know the definition of the product function? > > 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

3 2

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 20 Apr '09

20 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