July 2010 - Haskell-Cafe

Criteria for determining if a recursive function can be implemented in constant memory
by Steffen Schuldenzucker 06 Jul '10

06 Jul '10

Dear Cafe, since a little discussion with my tutor I am wondering how the following problem can be solved and if it is decidable: Given the definition of a recursive function f in, say, haskell, determine if f can be implemented in O(1) memory. First I thought the solution would be "check if f is tail-recursive". However, consider the following definition: > -- for the sake of uniformity > if' c t e = if c then t else e > > f :: (Num a) => a -> a -> a > f x y = if' (x <= 0) y $ > if' (x >= 2) (f (x-2) (y+1)) (f (x-1) y) (I don't really care what this function computes as long as it terminates, which is obvious) Although ghc will probably not perform this optimization, f can be realized in O(1) mem: // trying to duplicate f's structure as closely as possible double f( double x, double y ) { START: if ( x <= 0 ) return y; else { if ( x >= 2 ) { x = x - 2; y = y + 1; goto START; } else { x = x - 1; y = y; goto START; } } } It is crucial that (the second) if' does not use both of its last two arguments, but only one. If we replace the second if' by, say > g :: (Num a) => c -> a -> a -> a > g c t e = if' c (t + e) (t - e) , then we have to compute *both* (f (x-2) (y+1)) and (f (x-1) y), and x and y have to be kept in memory during the call to (f (x-2) (y+1)), therefore f cannot be implemented in constant memory. (read: I haven't found a way which does not radically alter f's structure). So, does someone know how to solve this or can prove that it can't be solved? Best regards, Steffen

5 6

Re: [Haskell-beginners] upgrade Hackage show to QuickCheck 2 for lambdabot
by Antoine Latter 06 Jul '10

06 Jul '10

Including the café. On Jul 2, 2010 8:49 AM, "Mark Wright" <markwright(a)internode.on.net> wrote: Hi, I'm trying to upgrade Hackage show to QuickCheck 2, after applying the diffs below (which may not be correct, since I am a beginner), I am left which this error message: runghc ./Setup.hs build Preprocessing library show-0.3.4... Building show-0.3.4... [4 of 4] Compiling ShowQ ( ShowQ.hs, dist/build/ShowQ.o ) ShowQ.hs:104:20: Not in scope: `generate' Compilation exited abnormally with code 1 at Fri Jul 2 23:07:17 The error occurs in this method: tests :: Gen Result -> StdGen -> Int -> Int -> [[String]] -> IO String tests gen rnd0 ntest nfail stamps | ntest == 500 = done "OK, passed" ntest stamps | nfail == 1000 = done "Arguments exhausted after" ntest stamps | otherwise = case ok result of Nothing -> tests gen rnd1 ntest (nfail+1) stamps Just True -> tests gen rnd1 (ntest+1) nfail (stamp result:stamps) Just False -> return $ "Falsifiable, after " ++ show ntest ++ " tests:\n" ++ reason result where result = generate (((+ 3) . (`div` 2)) ntest) rnd2 gen (rnd1,rnd2) = split rnd0 The QuickCheck 1 generate method is near the bottom this page: http://hackage.haskell.org/packages/archive/QuickCheck/1.2.0.0/doc/html/Tes… but I can not find generate in QuickCheck 2. I am wondering if you have any ideas on how to fix it? I'm trying to package lambdabot on Solaris. I have already packaged the Haskell Platform and about 90 packages, they are in: http://pkgbuild.sourceforge.net/spec-files-extra/ Thanks very much, Mark here are the diffs: goanna% diff -wc show-0.3.4-orig/ShowQ.hs show-0.3.4/ShowQ.hs *** show-0.3.4-orig/ShowQ.hs Wed Jan 20 11:24:11 2010 --- show-0.3.4/ShowQ.hs Fri Jul 2 23:07:13 2010 *************** *** 12,22 **** --- 12,25 ---- import qualified Test.SmallCheck (smallCheck, Testable) import Test.QuickCheck + import Test.QuickCheck.Arbitrary import Data.Char import Data.List import Data.Word import Data.Int import System.Random + import Control.Exception (evaluate) + import Test.QuickCheck.Property (ok, stamp) type T = [Int] type I = Int *************** *** 23,36 **** --- 26,45 ---- instance Arbitrary Char where arbitrary = choose (minBound, maxBound) + + instance CoArbitrary Char where coarbitrary c = variant (ord c `rem` 4) instance Arbitrary Word8 where arbitrary = choose (minBound, maxBound) + + instance CoArbitrary Word8 where coarbitrary c = variant (fromIntegral ((fromIntegral c) `rem` 4)) instance Arbitrary Ordering where arbitrary = elements [LT,EQ,GT] + + instance CoArbitrary Ordering where coarbitrary LT = variant 1 coarbitrary EQ = variant 2 coarbitrary GT = variant 0 *************** *** 37,42 **** --- 46,53 ---- instance Arbitrary Int64 where arbitrary = sized $ \n -> choose (-fromIntegral n,fromIntegral n) + + instance CoArbitrary Int64 where coarbitrary n = variant (fromIntegral (if n >= 0 then 2*n else 2*(-n) + 1)) instance (Integral a, Arbitrary a) => Arbitrary (Ratio a) where *************** *** 48,53 **** --- 59,65 ---- else (b % a) else (a % b) + instance (Integral a, CoArbitrary a) => CoArbitrary (Ratio a) where coarbitrary m = variant (fromIntegral $ if n >= 0 then 2*n else 2*(-n) + 1) where n = numerator m *************** *** 87,93 **** Just False -> return $ "Falsifiable, after " ++ show ntest ++ " tests:\n" ! ++ unlines (arguments result) where result = generate (((+ 3) . (`div` 2)) ntest) rnd2 gen (rnd1,rnd2) = split rnd0 --- 99,105 ---- Just False -> return $ "Falsifiable, after " ++ show ntest ++ " tests:\n" ! ++ reason result where result = generate (((+ 3) . (`div` 2)) ntest) rnd2 gen (rnd1,rnd2) = split rnd0 goanna% _______________________________________________ Beginners mailing list Beginners(a)haskell.org http://www.haskell.org/mailman/listinfo/beginners

2 2

Please check your dependencies on fgl
by Ivan Miljenovic 06 Jul '10

06 Jul '10

Thomas Bereknyei are currently re-writing fgl (just about completely from scratch) and we plan to make an initial release to get feedback on the API in the next few weeks. However, I'm sending this email out now to warn people that I highly doubt any code that was written for the current version of fgl (http://hackage.haskell.org/package/fgl-5.4.2.2) will work with the new version. As such, if your code uses fgl you should ensure that the specification of the package in your .cabal file has an explicit upper bound (or indeed just set "fgl == 5.4.2.2") to avoid any problems when we release 6.0.0.0 (we're trying to avoid the problems that plagued KDE-4 by not claiming in the slightest that the initial few versions are intended for end users). I have already directly emailed the maintainers of any and all packages I could find on Hackage (using Roel van Dijk's wonderful reverse-dependency mirror at http://bifunctor.homelinux.net/~roel/hackage/packages/hackage.html) but just in case I've missed one or there's an as-yet-unreleased package somewhere in the works, here is the official "heads up". -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

17 43

cereal vs. binary
by braver 06 Jul '10

06 Jul '10

I dump results of a computation as a Data.Trie of [(Int,Float)]. It contains about 5 million entries, with the lists of 35 or less pairs each. It takes 8 minutes to load with Data.Binary and lookup a single key. What can take so long? If I change from compressed to uncompressed (and then decode), it's the same time... It's not IO, CPU is loaded 100%. I'm now thinking of using cereal. Given I have Data.Binary in place, what needs to be changed to work with cereal? Is it binary- compatible? How can one construct a cereal instance for Data.Trie? -- Alexy

4 4

More experiments with ATs
by Andrew Coppin 06 Jul '10

06 Jul '10

Currently we have class Functor c where fmap :: (x -> y) -> (c x -> c y) This relies on c having kind * -> *. For example, Bytestring cannot be an instance of Functor. A cleaner solution would be to have something like class Container c where type Element c :: * I then attempted to write class Container c => Functor c where fmap :: (Functor cx, Functor cy, Element cx ~ x, Element cy ~ y) => (x -> y) -> (cx -> cy) However, this fails horribly: The type signature fails to mention c. And even if it did, this type signature still isn't correct: It says that fmap can transform *any* functor into *any* other functor, which is wrong. It seems that we have gained the ability to talk about containers holding any type of value (even hard-coded types or types with class constraints), but lost the ability to refer to a particular "type of" functor without also specifying the element type. Does anybody know a straightforward way to fix this? Or is this just a dead end?

7 10

emacs tags
by Michael Mossey 05 Jul '10

05 Jul '10

(I asked this question on the logical email list to ask, haskell-mode, but got no reply, so I'm hoping someone here might know the answer.) I tried to use tags with emacs. I ran :etags in ghci, then tried to use C-c M-. inside Emacs to find the definition of a symbol. It reported "no source information available". I did some basic checking---a TAGS file does exist in the same directory as the file I was visiting, and contains some kind of entry for the specific symbol (whether the right syntax I don't know). I'm using haskell-mode 2.4 and emacs 21.3.1 on Windows XP. Also ghci 6.12.1. Thanks, Mike

1 0

Is my code too complicated?
by Ertugrul Soeylemez 05 Jul '10

05 Jul '10

Hello fellow Haskellers, I'd like to discuss an interesting topic. My experience is that there are two worlds in Haskell, which are quite separate: the pure, algorithmic world, where you use idiomatic pure Haskell, and the IO-driven world of state, change, threads and execution, where you use idiomatic concurrent Haskell. If you understand these two concepts well, then you are usually a good Haskell programmer. Interestingly this doesn't mean that you get applications done faster or done at all. Most languages today provide a certain "glue" to bring everything together. I think that term originates from "Why Functional Programming Matters" by John Hughes. Haskell provides a lot of low level glue like laziness, currying and other very helpful language features. But what is different in Haskell is that it doesn't seem to provide any high level glue like other languages do, especially when it comes to the IO world. There is a somewhat powerful module system, but nothing to bring modules and the objects they define together in a consistent way. In my opinion this is both a disadvantage and an advantage. It's bad because there is no standard way of gluing, nothing everybody learns and uses. On the other hand it's good, because you can make your own glue. This has proven very useful for me. My usual way is writing monad transformers and sticking them together, often together with concurrent programming. The problem with that approach is: This makes my code harder to understand for beginners. Usually they can tell /what/ my code is doing, because it's written in natural language as much as possible, but they couldn't reproduce it. And when they try to learn it, they give up fast, because you need quite some background for that. Also sometimes when I write Haskell, my friend sits beside me and watches. When he asks (as a PHP programmer with some C background), say, about my types, I can't give a brief explanation like I could in other languages. Yesterday I was writing a toy texture handler for OpenGL (for loading and selecting textures). He asked about my TextureT type. I couldn't explain it, because you couldn't even express such a thing in PHP or C. type TextureT = StateT Config -- Note that this is MonadLib. -- BaseM m IO corresponds to MonadIO m. selectTexture :: BaseM m IO => B.ByteString -> TextureT m () I fear that my code is already too difficult to understand for beginners, and it's getting worse. But then I ask myself: I've got a powerful language, so why shouldn't I use that power? After all I haven't learnt Haskell to write C code with it. And a new Haskell programmer doesn't read my code to learn Haskell. They first learn Haskell and /then/ read my code. Is this a real problem or am I just exaggerating? What do you think? Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/

13 30

Getting started
by Mrwibbly 05 Jul '10

05 Jul '10

I'm having real trouble starting this project. Basically I have to create a record store that store information about artists and albums and also the number of sales that they have had. It also needs to generate a list of the top 5 sellers. So far I have: recordSale :: Sales -> String -> String -> Sales where recordSale sales anArtist aTrack returns a modified version of the sales. Any help getting started on this would be gratefully received. I don't want answers, I just want help getting started. Thank you -- View this message in context: http://old.nabble.com/Getting-started-tp29046956p29046956.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

5 10

Fwd: [Haskell-cafe] Re: Is my code too complicated?
by Alberto G. Corona 05 Jul '10

05 Jul '10

Very often the type system assures safety to a point where some coding is done trough trial and error: -I think that this composition is right, let´s try it-... -oh, some missing type here, Let´s put it here and here-...-go on-... -The typechecker say t´s OK. I run it and, well it works. Later when I look at the code, I have to think twice to understand it. Sometimes I mix transactions, threading, IO and some other abstractions in the same line, things that I would fear much to work with in any other language. This playing thig is fine, because the typechecking cut a lot of dead branches in the entrophic tendency of humans to commit mistakes. For this matter I praise math as the hidden god that handles reality and haskell its prophet. but the resulting code is not a product of my intended design, but something made together with the compiler, and sometimes it needs more than a look to understand it, even to myself. 2010/7/5 Ertugrul Soeylemez <es(a)ertes.de> Felipe Lessa <felipe.lessa(a)gmail.com> wrote: > > > On Sat, Jul 3, 2010 at 9:25 AM, Ertugrul Soeylemez <es(a)ertes.de> wrote: > > > Haskell provides a lot of low level glue like laziness, currying and > > > other very helpful language features. But what is different in > > > Haskell is that it doesn't seem to provide any high level glue like > > > other languages do, especially when it comes to the IO world. There > > > is a somewhat powerful module system, but nothing to bring modules > > > and the objects they define together in a consistent way. > > > > When I first read this paragraph, I thought: "STM to the rescue!". > > STM is one of the best concurrent world glues, IMHO. > > I found that I get along with the basic concurrency constructs. STM may > be handy in a few applications, but in none that I write. > > > > If you want, you may use Haskell just as you as PHP or C: just put > > everything in IO. Your code will get uglier and the type system won't > > catch many bugs, but that's what we get when doing C or PHP, right? > > Not really. Even when programming in such a style, Haskell is much > safer than PHP with its braindead type system, and still somewhat safer > than C. > > > > > The problem with that approach is: This makes my code harder to > > > understand for beginners. Usually they can tell /what/ my code is > > > doing, because it's written in natural language as much as possible, > > > but they couldn't reproduce it. And when they try to learn it, they > > > give up fast, because you need quite some background for that. Also > > > sometimes when I write Haskell, my friend sits beside me and > > > watches. When he asks (as a PHP programmer with some C background), > > > say, about my types, I can't give a brief explanation like I could > > > in other languages. > > > > I agree that it gets harder to reason about the code. In fact, > > sometimes I stack monad transformers in the wrong order. However, as > > Ivan says, if the feature is useful for you, don't be afraid of using > > it. Beginners may have a hard time grasping the concepts for the > > first time, but that's only until they "get it". > > I find monad transformers easy to reason about, and in most cases the > stacking order doesn't make a difference at all. Just remember to > change the running function, too. The problem with them is that > beginners learn them very late. > > > > > Yesterday I was writing a toy texture handler for OpenGL (for > > > loading and selecting textures). He asked about my TextureT > > > type. I couldn't explain it, because you couldn't even express such > > > a thing in PHP or C. > > > > > > type TextureT = StateT Config > > > > > > -- Note that this is MonadLib. > > > -- BaseM m IO corresponds to MonadIO m. > > > selectTexture :: BaseM m IO => B.ByteString -> TextureT m () > > > > "It is the type of functions that may access and modify a state of > > type Config." > > Then you need to explain "type of functions" and this explicitly > implicit "state" and why you have to do it that way in Haskell. > > > Greets, > Ertugrul > > > -- > nightmare = unsafePerformIO (getWrongWife >>= sex) > http://ertes.de/ > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

How easy is it to hire Haskell programmers
by Paul Johnson 05 Jul '10

05 Jul '10

I'm starting to see job adverts mentioning Haskell as a "nice to have", and even in some cases as a technology to work with. However right now I'm looking at it from the other side. Suppose someone wants to hire a Haskell developer or three. How easy is this? I'd appreciate replies from people who have actually done this. * How many applications did you get? * How many of those applicants knew what a monad is, or how to write FizzBuzz in Haskell? Thanks, Paul.

27 53