October 2010 - Haskell-Cafe

Eta-expansion destroys memoization?
by Brent Yorgey 12 Oct '10

12 Oct '10

Hi all, See below for this message from one of my students which has me stumped. Just when you think you understand Haskell... ;) I've cc'ed him on this message; please include him on any replies as I don't think he is subscribed to -cafe. -Brent ----- Forwarded message from Yue Wang <yulewang(a)gmail.com> ----- From: Yue Wang <yulewang(a)gmail.com> Date: Tue, 5 Oct 2010 21:23:57 -0400 To: Brent Yorgey <byorgey(a)seas.upenn.edu> Subject: store evaluated values Hi, Anthony (or Brent): Last time (in Anthony's TA office hour) we talked about how to store evaluated values in the program for later used. I googled for a while and wrote some code. But I still encountered two problems. Can you take a look? Thanks. First, let's write the naive fib function: naive_fib 0 = 0 naive_fib 1 = 1 naive_fib n = trace(show(n)) naive_fib (n - 1) + naive_fib (n - 2) this works good except it tries to calculate the same expression many times. So when we evaluate it ghci will show the following: *Main> naive_fib 5 5 4 3 2 2 3 2 5 Then there is a clever way to do that on haskell wiki: fib = ((map fib' [0 ..]) !!) where fib' 0 = 0 fib' 1 = 1 fib' n =trace(show(n)) fib (n - 1) + fib (n - 2) When we evaluate the same expression we can see it does not evaluate the redundant expression over and over: *Main> fib 5 5 4 3 2 5 The source code seems to be easy to read, but I don't think I understand that. For me I think if I change the first line from fib = ((map fib' [0 ..]) !!) to fib x = ((map fib' [0 ..]) !!) x It should do the same thing since I think the previous version is just an abbreviation for the second one. But After I change that, *Main> fib 5 5 4 3 2 2 3 2 5 So why does the x here matters?

11 11

RealFrac methods for Double and Float
by Daniel Fischer 11 Oct '10

11 Oct '10

Greetings, I have put together a package to test possible implementations of the RealFrac methods for Double and Float (base-2 IEEE754) and uploaded a .tar.gz bundle to http://hackage.haskell.org/trac/ghc/ticket/2271 . On the one hand, pure Haskell implementations, on the other hand implementations calling out to rint[f], trunc[f], floor[f] and ceil[f] from math.h. Both ways go via Integer by default, with a specialised faster implementation for Int (and narrower types, but those RULES haven't yet been written) enabled by a rewrite rule. Overall, the pure Haskell implementations don't fare badly on my computer. All give a speedup compared to the current implementation, for most conversions, pure Haskell is on par with or faster than the C-call (although that would probably change if the C functions were made primops). The FFI calls are significantly faster for properFraction :: Double -> (Integer, Double) and for round (except round :: Integral a => Float -> a when compiled via C, then native and FFI are on par). Sample results for the speedups against the current implementation (note: for truncate :: x -> Int, the Prelude value is fst . properFraction, not the rewritten float2Int or double2Int) are included in the tarball. I would appreciate feedback from your tests/benchmarks on other platforms, especially 64-bit platforms (mine is x86 linux, 32 bit). To run the QuickCheck tests, you need QuickCheck-2.*, to run the benchmarks, criterion. More instructions in the README. Thanks, Daniel

2 6

Static computation/inlining
by Alexander Solla 11 Oct '10

11 Oct '10

Hi everybody, I'm working on a module that encodes "static" facts about "the real world". For now, I'm working on an ISO 3166 compliant list of countries, country names, and country codes. I've run into a bit of an optimization issue. There is a static bijective correspondence between countries and their codes. In order to keep one just one "large" data structure representation as Haskell code, I encoded this bijection using a list. I'm looking to write queries against this list, but it is rather tedious. I figured I could make some Data.Maps to handle it for me. -- Country and ISOCountryCodes derive (Data, Eq, Ord, Show, Typeable) countries_and_iso_country_codes :: [ (Country, ISOCountryCode) ] countries_and_iso_country_codes = [ ( Afghanistan , ISOCountryCode AF AFG (isoNumericCode 004) ) , ( AlandIslands , ISOCountryCode AX ALA (isoNumericCode 248) ) , ( Albania , ISOCountryCode AL ALB (isoNumericCode 008) ) ... , ( Zimbabwe , ISOCountryCode ZW ZWE (isoNumericCode 716) ) ] map_country_to_country_code :: Map Country ISOCountryCode map_country_to_country_code = fromList countries_and_iso_country_codes map_country_code_to_country :: Map ISOCountryCode Country map_country_code_to_country = fromList . fmap (\(a,b) -> (b, a)) $ countries_and_iso_country_codes Is there anyway to instruct GHC (and maybe other compilers) to compute these maps statically? Are GHC and the other compilers smart enough to do it automatically? Although the list isn't huge, I would still rather get rid of the O(2*n) operation of turning it into maps at run- time. (Especially since some later list encodings like these might be enormous) What should I be looking into? Thanks

4 3

pointers for EDSL design
by oleg＠okmij.org 11 Oct '10

11 Oct '10

John Lato wrote: > So here's a very simple expression: > > t1 = let v = sigGen (cnst 1) in outs v v > > which is what led to my question. I'm binding the sigGen to 'v' to > introduce sharing at the meta-level. Would it be better to introduce > support for this in the dsl? Often this is not a question of preference but that of necessity. Sharing at the meta-level may help the generator, but it does _not_ translate into the sharing at the object level. In the generated code, the code for 'sigGen (cnst 1)' shall be duplicated. It could be that two csound blocks must share the same signal source, to receive samples in parallel. Meta-level sharing (Haskell's let) would not do. We need a construct for an object-level let, for example t1 = let_ (SigGen (cnst 1)) (\v -> outs v v) (Template Haskell can improve the syntax.) The term `off-shoring' was coined by Walid Taha and collaborators, and first appeared in the paper Implicitly Heterogeneous Multi-Stage Programming. GPCE'05 (whose first draft was written in Feb 2004).

3 2

Re: Round benchmarks
by Daniel Fischer 11 Oct '10

11 Oct '10

On Monday 11 October 2010 07:05:20 you wrote: > Hi, > > These results seem different from the samples. Thanks. The numbers are quite impressive. Although the quotients (hence speedups) are generally much larger, the ranking doesn't differ much. For round :: x -> Int, via C is a big win. For round :: x -> Integer and properFraction :: Double -> (Integer, Double), going via C doesn't seem to make much difference on 64 bits, but they do on 32. That's probably because a Double mantissa is a smallInteger on 64 bits. Overall, your timings support going via C for round and properFraction :: Double -> (Integer, Double). In two cases, it makes not much difference on 64 bits but is a big gain on 32, for round :: x -> Int, it's a big win on both. > > I was surprised that the "via Integer" results appear faster than the > Int results. No, the numbers are (Prelude time / new time), so the larger the number, the better. Sorry for not making that clear in the README. > > Vivian Cheers, Daniel

1 0

Re: [Haskell-cafe] Haskellers.com recent changes (and I need some volunteers)
by Mark Lentczner 11 Oct '10

11 Oct '10

On Oct 10, 2010, at 10:56 AM, Michael Snoyman wrote: > I'm worried about spam accounts being featured on > the homepage. Real Haskeller is not meant to be exclusive, it's a > minimal level of oversight by the admins. A more common approach to the problem of spam accounts -- which is very real -- is to not allow accounts to appear before they have been vetted by an admin. Allowing accounts to appear on the site as they are created will, sooner or later, result in the site being over run with spam faster than you can keep up. For the community site I help run (http://www.contextfreeart.org/) had this problem a while back and we switched to all accounts being vetted. We use http://www.stopforumspam.com/ as source of information to easily help us make that determination. - Mark

2 1

Haskellers.com recent changes (and I need some volunteers)
by Michael Snoyman 10 Oct '10

10 Oct '10

Hey all, Haskellers became popular a lot faster than I'd anticipated. This has prompted me to need to make some changes that I was only planning on implementing later on. As usual, all points are up for discussion (this is intended to be a community-run site after all). * Pagination on homepage. We now see only 10 users at a time. * The sort order is different. Now, "real haskellers" (we'll discuss that in a second) come first, sorted by years of experience with Haskell and then alphabetically by full name. * We now have site admins. Currently, I'm the only one, but I would like to add some more (thus the need for volunteers). Admins currently have four rights/duties: * Grant/revoke "real haskeller" status. This status currently only affects sort order on home page, but might be used for more in the future. * Grant/revoke admin rights. * Block/unblock a user. A blocked user will not show up on the homepage, not be counted for public/private/unverified accounts, and will have a big nasty "blocked" warning on their user page. * Read/close admin messages. These can be created by the following features: * Users can request "real haskeller" status in their Edit Profile > Extras tab. * Users can request their account to be unblocked. * Anyone (logged in or not) can flag a user on their user page. You'll notice that admins are not able to make any changes to user data. Anyone who is interested in taking on this responsibility should email me about it. I think five people should easily be able to handle this, I'm not anticipating a high load. Then again, I didn't anticipate over 200 accounts created in a week either. Oh, and *please* don't email me personally to request a "real Haskeller" status. If you use the button on the site, it makes it much easier to add the status. Also, don't take it personally if an admin denies your "real haskeller" request; it's currently a very poorly defined notion, and I don't even know who the admins are going to be. Michael

4 3

My knight's tour does not seem to end
by C K Kashyap 10 Oct '10

10 Oct '10

Hi, I tried an implementation of knight's tour and it does not seem to terminate. I am looking for some feedback on algorithm and Haskellness of my implementation (knight.hs attached). -- Regards, Kashyap

3 6

Polyvariadic functions operating with a monoid
by oleg＠okmij.org 10 Oct '10

10 Oct '10

Kevin Jardine wrote: > instead of passing around lists of values with these related types, I > created a polyvariadic function polyToString... > I finally figured out how to do this, but it was a bit harder to > figure this out than I expected, and I was wondering if it might be > possible to create a small utility library to help other developers do > this. > It seems to me that in the general case, we would be dealing with a > Monoid rather than a list of strings. We could have a toMonoid > function and then return > > polyToMonoid value1 value2 ... valueN = > > (toMonoid value1) `mappend` (toMonoid value2) 'mappend' ... (toMonoid > valueN) > So I tried writing the following code but GHC said it had undecidable > instances. Generally speaking, we should not be afraid of undecidable instances: it is a sufficient criterion for terminating type checking but it is not a necessary one. A longer argument can be found at http://okmij.org/ftp/Haskell/types.html#undecidable-inst-defense However, the posted code has deeper problems, I'm afraid. First, let us look at the case of Strings: > class PolyVariadic p where > polyToMonoid' :: String -> p > > instance PolyVariadic String where > polyToMonoid' acc = acc > > instance (Show a, PolyVariadic r) => PolyVariadic (a->r) where > polyToMonoid' acc = \a -> polyToMonoid' (acc ++ show a) > > polyToMonoid :: PolyVariadic p => p > polyToMonoid = polyToMonoid' mempty > > test1 = putStrLn $ polyToMonoid True () (Just (5::Int)) *M> test1 True()Just 5 Modulo the TypeSynonymInstances extension, it is Haskell98. If we now generalize it to arbitrary monoids rather than a mere String, we face several problems. First of all, if we re-write the first instance as > instance Monoid r => PolyVariadic r where > polyToMonoid' acc = acc we make it overlap with the second instance: the type variable 'r' may be instantiated to the arrow type a->r'. Now we need a more problematic overlapping instances extension. The problem is deeper however: an arrow type could possibly be an instance of Monoid (for example, functions of the type Int->Int form a monoid with mempty=id, mappend=(.)). If polyToMonoid appears in the context requiring a function type, how could type checker choose the instance of Polyvariadic? The second problem with the posted code > class Monoidable a where > toMonoid :: Monoid r => a -> r is that toMonoid has too `strong' a signature. Suppose we have an instance > instance Monoidable String where > toMonoid = \str -> ??? It means that no matter which monoid the programmer may give to us, we promise to inject a string into it. We have no idea about the details of the monoid. It means that the only thing we could do (short of divergence) is to return mempty. That is not too useful. We have little choice but to parametrise Monoidable as well as Polyvariadic with the type of the monoid. To avoid overlapping and disambiguate the contexts, we use the newtype trick. Here is the complete code. It turns out, no undecidable instances are needed. > {-# LANGUAGE TypeSynonymInstances #-} > {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} > > module M where > > import Data.Monoid > > newtype WMonoid m = WMonoid{unwrap :: m} > > class Monoid m => Monoidable a m where > toMonoid :: a -> m > > class Monoid m => PolyVariadic m p where > polyToMonoid :: m -> p > > instance Monoid m => PolyVariadic m (WMonoid m) where > polyToMonoid acc = WMonoid acc > > instance (Monoidable a m, PolyVariadic m r) => PolyVariadic m (a->r) where > polyToMonoid acc = \a -> polyToMonoid (acc `mappend` toMonoid a) > > instance Show a => Monoidable a String where > toMonoid = show > > test2 = putStrLn $ unwrap $ polyToMonoid "" True () (Just (5::Int)) The remaining problem is how to tell polyToMonoid which monoid we want. It seems simpler just to pass the appropriately specialized mempty method as the first argument, as shown in test2. Granted, a more elegant solution would be a parametrized module (functor) like those in Agda or ML: module type PolyM = functor(M:: sig type m val mempty :: m val mappend :: m -> m -> m end) = struct class Monoidable a where toMonoid :: a -> m class PolyVariadic p where polyToMonoid :: m -> p .etc end The shown solution is essentially the encoding of the above functor.

4 13

Re-order type
by André Batista Martins 10 Oct '10

10 Oct '10

Hello, exists any algorithm to determine how terms can be changed to safisty the type of one function? example: f:: a-> b -> c -> (b,c,a) f1 :: c -> a -> d In my first function "f" i want assign the output "c" and "a" for to input of function "f1". I searched for any solution, but i didn't find any anything. One clue i have found is "minimal edit distance algorithm" for 2 strings. Perhaps if i convert de output type of "f" to one string, and de input of "f1" to another string and then use this algorithm , i will get one "dirty" solution... I'm open to any sugestion.

3 2