[Haskell-cafe] Rewriting ord (revisited)
Hi This was my original version plus some modifications as advised by the list: f c = sum [1 | x - ['\0'..], x c] The following version was sent by a list member: f c = length $ takeWhile (c) ['\0'..] Now, the sender asserted that the first version was much too slow. I'm wondering how the second version is any more efficient than the first. Looking at them through my C programmers' eye, as it were, both would require at least two loops before returning the ANSI value. Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting ord (revisited)
The second version looks very neat, certainly, though I am not entirely convinced that it's any more efficient. Still, I may be missing something. The compiler must be one hell of a machine. I wonder if the source code is available to the public. Cheers, Paul At 12:26 30/09/2007, you wrote: -BEGIN PGP SIGNED MESSAGE- Hash: RIPEMD160 I would think that the compiler is smart enough to fuse the two loops. That doesn't explain the performance difference though. Adrian PR Stanley schrieb: Hi This was my original version plus some modifications as advised by the list: f c = sum [1 | x - ['\0'..], x c] The following version was sent by a list member: f c = length $ takeWhile (c) ['\0'..] Now, the sender asserted that the first version was much too slow. I'm wondering how the second version is any more efficient than the first. Looking at them through my C programmers' eye, as it were, both would require at least two loops before returning the ANSI value. Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFG/4f+11V8mqIQMRsRAxegAJ4t5grdRDrWVWby6tjDZDdxgJ72FQCfcD7W Mntl7FV2GpCGtpY2yP61kbk= =l+3X -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting ord (revisited)
On 9/30/07, PR Stanley [EMAIL PROTECTED] wrote: Hi This was my original version plus some modifications as advised by the list: f c = sum [1 | x - ['\0'..], x c] The following version was sent by a list member: f c = length $ takeWhile (c) ['\0'..] Now, the sender asserted that the first version was much too slow. I'm wondering how the second version is any more efficient than the first. Looking at them through my C programmers' eye, as it were, both would require at least two loops before returning the ANSI value. Any ideas? It's very simple. You know that ['\0'..] is in ascending order, of course. So, if you want all elements ( c), then they must be a prefix of that list. IOW, after you found the first x in ['\0'..] such that x c == False, then you know that all the elements following x will also be greater than c, as they are greater then x and the operator () is transitive. In the first version, you traverse the entire list looking for those elements, no matter what c you give. OTOH, the second traverse only (ord c + 1) elements, stopping after reaching some x = c, and it would also work even if ['\0'..] were infinite, e.g: Prelude let c = 42 :: Integer -- Integers are unbounded Prelude takeWhile ( c) [0..] [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41] Prelude length $ takeWhile ( c) [0..] 42 Prelude [1 | x - [0..], x c] [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1Interrupted. Prelude sum [1 | x - [0..], x c] Interrupted. Note that the second list will wait forever for the list comprehension to finish before it can be seen that after those 42 ones there's the empty list []. HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Rewriting filter with foldr
Hi filter :: (a - Bool) - [a] - [a] filter f = foldr (\x - \xs - if (f x) then (x:xs) else xs) [] Somehow I feel this could be done more elegantly. What does the list think? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting ord (revisited)
The compiler must be one hell of a machine. I wonder if the source code is available to the public. It is, and it is. =) http://hackage.haskell.org/trac/ghc/wiki/Building/GettingTheSources -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting filter with foldr
Perhaps a list comprehension better shows the intention of the filter function: filter p xs = [x | x - xs, p x] You can literally read that as take all x from xs that satisfy p. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting filter with foldr
On 9/30/07, PR Stanley [EMAIL PROTECTED] wrote: Hi filter :: (a - Bool) - [a] - [a] filter f = foldr (\x - \xs - if (f x) then (x:xs) else xs) [] Somehow I feel this could be done more elegantly. What does the list think? Thanks, Paul Well, note that foldr takes a function of x, which produces a function of xs. This function of xs either conses x onto it, or leaves it unchanged. We can write this down explicitly by removing the xs parameter and just writing what function should be produced: filter f = foldr (\x - if (f x) then (x:) else id) [] -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting filter with foldr
The question is asking for a new definition of filter using foldr. Sorry, I should have mentioned that before. Cheers, Paul At 14:26 30/09/2007, you wrote: Perhaps a list comprehension better shows the intention of the filter function: filter p xs = [x | x - xs, p x] You can literally read that as take all x from xs that satisfy p. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Compose
Hi sumSquareEven = (sum.map (^2)).filter even I wrote this thinking i was being very clever. The question is asking to spot the error in f = compose [sum, map (^2), filter even] I've only seen [] used in list comprehension and initialisation. I conducted a mini search on compose earlier but to be honest it just made matters even less clear. So the question is, does compose as a function or keyword exist in Haskell and if so how can the above code frag be corrected? O and, is compose in any way related to curry and uncurry? Thanks v mucho, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compose
On 9/30/07, PR Stanley [EMAIL PROTECTED] wrote: So the question is, does compose as a function or keyword exist in Haskell and if so how can the above code frag be corrected? O and, is compose in any way related to curry and uncurry? You can't write that function in Haskell as the list is heterogeneous. If all functions were of the same type, then you could do something like compose :: [a - a] - (a - a) compose = foldr (.) id HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting filter with foldr
Well, note that foldr takes a function of x, which produces a function of xs. This function of xs either conses x onto it, or leaves it unchanged. We can write this down explicitly by removing the xs parameter and just writing what function should be produced: filter f = foldr (\x - if (f x) then (x:) else id) [] That's one neat solution but it also raises a few questions for me: foldr :: (a - b - b) - b - [a] - b yet you've managed to squeeze in a function that takes only one argument. How is this possible without GHCI blowing its top? 2. Could you please explain the role of the identity function (id) in your code? Where's its argument, or is it sort of implicitly noted? For example, is it the case that the second argument is held in reserve and passed to the first function which would take it, hence (x:) and id? Many thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting filter with foldr
On Sep 30, 2007, at 11:57 , PR Stanley wrote: Well, note that foldr takes a function of x, which produces a function of xs. This function of xs either conses x onto it, or leaves it unchanged. We can write this down explicitly by removing the xs parameter and just writing what function should be produced: filter f = foldr (\x - if (f x) then (x:) else id) [] That's one neat solution but it also raises a few questions for me: foldr :: (a - b - b) - b - [a] - b yet you've managed to squeeze in a function that takes only one argument. How is this possible without GHCI blowing its top? 2. Could you please explain the role of the identity function (id) in your code? Where's its argument, or is it sort of implicitly noted? For example, is it the case that the second argument is held in reserve and passed to the first function which would take it, hence (x:) and id? Many thanks, Paul Those are the same question, actually. He is returning a function which takes one argument (either the partial application / section (x:) which expects a list argument, or the function id which expects any argument and returns it unmodified); since one argument is left unconsumed, that typechecks. (This is, after all, functional programming; returning functions is not only possible, but encouraged.) This follows from the fact that all (normal) Haskell functions are curried, so (\x y - something) is the same as (\x - (\y - something)), i.e. a 2-argument function is really a 1-argument function which returns a 1-argument function. Contrariwise, any time a 2-argument function is expected you can instead pass a 1-argument function which returns a 1-argument function. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting filter with foldr
filter f = foldr (\x - if (f x) then (x:) else id) [] That's one neat solution but it also raises a few questions for me: foldr :: (a - b - b) - b - [a] - b yet you've managed to squeeze in a function that takes only one argument. How is this possible without GHCI blowing its top? Someone already explained this so I'll skip it. 2. Could you please explain the role of the identity function (id) in your code? Where's its argument, or is it sort of implicitly noted? For example, is it the case that the second argument is held in reserve and passed to the first function which would take it, hence (x:) and id? How about working through an example? [I'm using notes on the left hand side. a number starting with a colon is a reference to a definition, and a word followed by a close paren ) is a justification for the step.] 1: filter f = foldr (\x - if (f x) then (x:) else id) [] 2: foldr k z xs = go xs 3: where go [] = z 4: go (y:ys) = y `k` go ys filter ( 3) [5,2,6] 1) = foldr (\x - if ( 3) x then (x:) else id) [] [5,2,6] 2) = go [5,2,6] where 5: go [] = [] 6: go (y:ys) = (\x - if ( 3) x then (x:) else id) y (go ys) 6) = (\x - if ( 3) x then (x:) else id) 5 (go [2,6]) lambda) = (if ( 3) 5 then (5:) else id) (go [2,6]) if) = (5:) (go [2,6]) 6) = (5:) ((\x - if ( 3) x then (x:) else id) 2 (go [6])) lambda) = (5:) (if ( 3) 2 then (2:) else id) (go [6])) if) = (5:) (id (go [6])) id) = (5:) (go [6]) 6) = (5:) ((\x - if ( 3) x then (x:) else id) 6 (go [])) lambda) = (5:) (if ( 3) 6 then (6:) else id) (go [])) if) = (5:) ((6:) (go [])) 5) = (5:) ((6:) []) (6:))= (5:) [6] (5:))= [5, 6] So you can see that its building up a chain of one-argument functions such as: (5:) (id ((6:) [])) before collapsing it down to a list like [5,6] (note to save space, I collapsed the id term early. If I left it till longer we would have arrived at the expression above). Many thanks, Paul Tim Newsham http://www.thenewsh.com/~newsham/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Extract source code from literate Haskell (LHS) files
This is of course very easy to do manually, but does a command line tool exist for extracting source code from literate Haskell files? Thanks, Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Extract source code from literate Haskell (LHS) files
On Sep 30, 2007, at 14:39 , Peter Verswyvelen wrote: This is of course very easy to do manually, but does a command line tool exist for extracting source code from literate Haskell files? unlit in the GHC library directory? -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Extract source code from literate Haskell (LHS) files
This is of course very easy to do manually, but does a command line tool exist for extracting source code from literate Haskell files? something like: sed -e '/^[^]/d' -e 's/^//g' foo.lhs foo.hs the first expression deletes lines not starting with . The second expression removes the at the beginning of each line. or if you prefer to keep the comments: sed -e 's/^[^]/-- /g' -e 's/^//g' foo.lhs foo.hs the first expression puts -- at the start of each line without a . Thanks, Peter Tim Newsham http://www.thenewsh.com/~newsham/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Extract source code from literate Haskell (LHS) files
Peter Verswyvelen bf3 at telenet.be writes: to do manually, but does a command line tool exist for extracting source code from literate Haskell files? Thanks, Peter lhs2tex will do this for you. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yampa question
On 9/29/07, Ryan Ingram [EMAIL PROTECTED] wrote: first bc = SF sf where sf dt ~(b,d) = ((c,d), sfFirst bc') where (c, bc') = runSF bc dt b One question I had was about the implementation of first. Is it important that the pair match be lazy? Or is it safe to make it strict? What are the advantages and disadvantages of each choice? The pattern match has to be lazy to make ArrowLoop/loop work. but there's a pretty clear space leak here with repeated Right calls, and I'm not sure if the inner signal should see the lost time or not. In the original implementation, the inner signal function is suspended or frozen in time when the input stream is not selecting it. While your implementation wants the inner signal function to remember and recover the lost time when it's not selected. This would require the inner signal function to handle arbitarily large delta time by itself though. I guess either would make sense in different situations, so the decision is purely yours. Also you should be able to make the leak go away by forcing the accumulated delta time to be fully evaluated before being passed on. Regards, Paul Liu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] The kind of (-)
Hi Guys! According ghci the kind of (-) is ?? - ? - * What do the '??' mean? What is the difference between the '?' and the '*' Cheers -- -Jeeva ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The kind of (-)
On Mon, Oct 01, 2007 at 11:40:20AM +1000, jeeva suresh wrote: Hi Guys! According ghci the kind of (-) is ?? - ? - * What do the '??' mean? What is the difference between the '?' and the '*' It's an implementation detail leaking out. GHC uses a set of special types to represent primitive values, and uses the kind system to enforce that they are never used as normal types. ? refers to ANYTHING, * refers only to normal types, and ?? refers to normal types and some of the special types. This is similar to the way that statically typed OO languages allow values of subclass types to be used as if they had superclass types. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
