Re: [Haskell-cafe] Memoization/call-by-need
Alex Rozenshteyn schrieb: I feel that there is something that I don't understand completely: I have been told that Haskell does not memoize function call, e.g. slowFib 50 will run just as slowly each time it is called. However, I have read that Haskell has call-by-need semantics, which were described as lazy evaluation with memoization http://www.haskell.org/haskellwiki/Memoization ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Introducing The Monads Presentation Slides
Matthias Kilian schrieb: On Fri, Sep 17, 2010 at 12:54:29PM -0500, aditya siram wrote: Slides shared and Reddited! Feedback is very welcome! http://www.reddit.com/r/haskell/comments/dfazp/introducing_the_monads_a_practical_tour_of/ Oh, come on. A site where you need a flash player to download (or view) a PDF? This is the most stupid concept I've seen in the last 24 hours. It would be nice if we could upload files to HaskellWiki. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Christopher Tauss schrieb: I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. Looking through the glasses of lazy evaluation, I would use my utility-ht:Data.List.Match module and write lastn n xs = ListMatch.drop (drop n xs) xs (ListMatch.drop ls xs) drops as many elements from xs as are in ls in the most lazy way. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
2010/9/18 Daniel Fischer daniel.is.fisc...@web.de n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). T No!. You forget laziness!. it is 0(n) with n= the parameter passed to n_lastn. It is not O(length list). the reversed and de-reversed elements are just the ones being taken , not the whole list. (please kill me if I´m wrong. I don´t want to live in a world where beauty is inneficient) ;) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Luke Palmer schrieb: I think this is O(n) time, O(1) space (!). lastk :: Int - [a] - [a] lastk k xs = last $ zipWith const (properTails xs) (drop k xs) where properTails = tail . tails If (drop k xs) is empty, this yields an error when calling 'last'. This might be a bug or a feature. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Hi Alberto, On 20.09.2010, at 10:53, Alberto G. Corona wrote: 2010/9/18 Daniel Fischer daniel.is.fisc...@web.de n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). T No!. You forget laziness!. it is 0(n) with n= the parameter passed to n_lastn. It is not O(length list). the reversed and de-reversed elements are just the ones being taken , not the whole list. (please kill me if I´m wrong. I don´t want to live in a world where beauty is inneficient) I am afraid you are argumentation is wrong. Let's see: f :: [a] - a f = head . reverse This is a function running in O(n) time, where n is the length of given list. That is, because f has to follow at least n pointers in order to reach the end of the parameter list. It might be much more expensive if the list has to be computed, because f got only a thunk to cumpute a list instead of a finished list. Lazyness helps helps to reduce work if your input list is lazily constructed and your function forces the returned element. Then you don't have to force all elements of the list, only the last one. Let's say l = [e_0, ..., e_n]. All the e_i are expensive calculations. g :: [a] - a g xs = x `seq` x where x = head (reverse xs) In order to compute g l you only have to evaluate e_n, not all the other e_i. Hope this helps. Jean ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell/JDK/tail-calls etc. (please vote on bug No. 6804517)
Compiling haskell for the JVM has been done before, several times. Sometimes even inside GHC.See for instance http://portal.acm.org/citation.cfm?id=968549 http://wwwspringerlink.com/content/w81yd3fljbrevuje/ http://www.mail-archive.com/hask...@haskell.org/msg06673.htmlRegards,Malcolm Even if tail recursion is not properly supported, I've never really understood why this is an *total* impediment to getting it working on the JVM. I mean, yes it sucks, but there are ways to do it anyway (trampolining for one). They are usually _slow_ methods (which trampoline is), but if it's the difference between being able to run on the JVM and not, you would think that someone would think running on JVM slowly is better than not running on it at all... Maybe that's not the case though, maybe it would actually be bad for Haskell's rep to run slowly on JVM compared to other languages. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: ieee version 0.7
On Monday 20 September 2010 06:47:12, John Millikin wrote: On Sun, Sep 19, 2010 at 21:43, Patrick Perry patpe...@gmail.com wrote: I needed real IEEE754 binary support for round-trip parsing, where (for example) maintaining the particular bit pattern of a NaN is important. For 99% of people, the unsafe method will work fine. How does a C-style cast not preserve the bit pattern of a NaN? Again, sorry if this is a stupid question. It's not a stupid question, and I don't know the answer. But if you plug a C-style cast into the data-binary-ieee754 unit tests, some of them (the fiddly ones, like roundtripping -NaN) will fail. Presumably, this is due to some optimization deep in the bowels of GHC, but I don't understand even a fraction of what goes on in there. For what it's worth, d-b-ieee754 was the very first Haskell library I ever wrote -- and it shows. If anybody knows how to make unsafeCoerce (or equivalent) roundtrip-safe, I would love to rip out all the ugly and make it sane. unsafeCoerce is not supposed to work for casts between Integral and Floating types. If you try to unsafeCoerce# between unboxed types, say Double# and Word64#, you're likely to get a compile failure (ghc panic). If you unsafeCoerce between the boxed types, it will probably work, but there are no guarantees. There's a feature request for unboxed coercion (i.e. reinterpretation of the bit-pattern): http://hackage.haskell.org/trac/ghc/ticket/4092 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Unified Haskell login
On Sun, 2010-09-19 at 17:12 +0200, Michael Snoyman wrote: Let me respond to this directly since a number of people have brought this up: Due to spam reasons we can't trust the email given via an OpenID provider in general. For example, it would be trivial for me to create an OpenID provider for myself, set my email address as insert someone else's address here and essentially spam them. By going with a service like Facebook or Google, we know (or at least assume) that they do proper email validation, so we could immediately accept this value without needing to verify it ourselves. In other words: Yes, I know there are extensions to OpenID. And no, we can't use it to get a verified email address. Michael There are people who for whatever reason don't use Facebook/Google/ And sending verification e-mail costs practically nothing. Regards PS. If we have on-site registration it would have unverified e-mail as well. signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: ieee754 version 0.7.1
Upon popular request, I've renamed the ieee package to ieee754. The new hackage page is http://hackage.haskell.org/package/ieee754 . On Sep 19, 2010, at 11:16 PM, Conrad Parker wrote: On 20 September 2010 11:18, Patrick Perry patpe...@gmail.com wrote: Given that IEEE is actually a standards body and they have many standards, wouldn't it be more appropriate to call this library ieee754? If it seems important to people, I'd be happy to change the name. I'm not religious about these things. Will it clutter up hackage, though? I reckon it's worth making it obvious that this library does 754 and not, say, 1394 or 802.11 ;-) On the other hand if you intend on expanding the package to implement every IEEE standard ... (j/k) Anyway, good work. Does this have any overlap with data-binary-ieee754? There was some recent discussion here about the encoding speed in that package. Conrad. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Unified Haskell login
On Mon, Sep 20, 2010 at 2:06 PM, Maciej Piechotka uzytkown...@gmail.com wrote: On Sun, 2010-09-19 at 17:12 +0200, Michael Snoyman wrote: Let me respond to this directly since a number of people have brought this up: Due to spam reasons we can't trust the email given via an OpenID provider in general. For example, it would be trivial for me to create an OpenID provider for myself, set my email address as insert someone else's address here and essentially spam them. By going with a service like Facebook or Google, we know (or at least assume) that they do proper email validation, so we could immediately accept this value without needing to verify it ourselves. In other words: Yes, I know there are extensions to OpenID. And no, we can't use it to get a verified email address. Michael There are people who for whatever reason don't use Facebook/Google/ And sending verification e-mail costs practically nothing. Regards PS. If we have on-site registration it would have unverified e-mail as well. From my original email: * Username/password on the site. But who wants to deal with *another* password? * OpenID. Fixes the extra password problem, but doesn't give us any extra information about the user (email address, etc). * Facebook/Twitter/Google: We get the users email address, but do we *really* want to force users to have one of those accounts? I disagree with the sentiment of sending a verification e-mail costs practically nothing. While *sending* it is cheap, we then need to wait for users to respond to it. Compare this with a Google/Facebook login scenario, where they click a button on our site, click approve on Google/Facebook, and are completely approved. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: ieee754 version 0.7.1
On Mon, Sep 20, 2010 at 2:23 PM, Patrick Perry patpe...@gmail.com wrote: Upon popular request, I've renamed the ieee package to ieee754. The new hackage page is http://hackage.haskell.org/package/ieee754 . You might wan't to deprecate the old ieee package so that it isn't shown in the package list anymore. (Mail Ross Paterson about that) Regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] example in All about Monads
Also keep in mind that Maybe is a sort of a toy example of the concept being developed. It is indeed useful as a monad in its own right, but certainly not a case where the comb function is absolutely essential, as wren demonstrated. There are stronger motivations for using the 'comb' approach in cases where the type in place of 'Maybe' is more complex, or even completely abstract so you can't match against its constructors directly. -- James On Sep 17, 2010, at 11:26 PM, wren ng thornton wrote: On 9/17/10 12:48 PM, ender wrote: my question is, why not define the function father and mother as type of father::Maybe Sheep - Maybe Sheep? this can also clean the code and it avoid the additional function comb Do note that `comb` is giving you a natural way of creating those functions: flip comb :: (a - Maybe a) - (Maybe a - Maybe a) Since we can define comb, every (a - Maybe a) has an associated function of type (Maybe a - Maybe a). And if we use comb, then that means we can use the function at either type, just pick whichever one is easier for us to use at the time. If we only ever defined (Maybe a - Maybe a) functions then we'd need to use a combinator to go the other way... f :: a - Maybe a g :: Maybe a - Maybe a f = ... g = flip comb f -- or -- f = g . Just g = ... Whether we use (flip comb) or (. Just) doesn't really matter too much. The point is that we can go both ways. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On Sep 20, 2010, at 5:10 AM, Jean-Marie Gaillourdet wrote: Hi Alberto, On 20.09.2010, at 10:53, Alberto G. Corona wrote: 2010/9/18 Daniel Fischer daniel.is.fisc...@web.de n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). T No!. You forget laziness!. it is 0(n) with n= the parameter passed to n_lastn. It is not O(length list). the reversed and de-reversed elements are just the ones being taken , not the whole list. (please kill me if I´m wrong. I don´t want to live in a world where beauty is inneficient) I am afraid you are argumentation is wrong. Let's see: f :: [a] - a f = head . reverse This is a function running in O(n) time, where n is the length of given list. That is, because f has to follow at least n pointers in order to reach the end of the parameter list. It might be much more expensive if the list has to be computed, because f got only a thunk to cumpute a list instead of a finished list. I don't believe he was claiming O(n) time, only O(n) space, which I am inclined to believe. Your 'f' should also run in O(1) space. In general, there can be no function depending in any way on the location of the end of the list that isn't O(length list) time, because if nothing else the end of the list must be discovered, which requires that much time no matter what the algorithm. Lazyness helps helps to reduce work if your input list is lazily constructed and your function forces the returned element. Then you don't have to force all elements of the list, only the last one. Let's say l = [e_0, ..., e_n]. All the e_i are expensive calculations. g :: [a] - a g xs = x `seq` x where x = head (reverse xs) Can x `seq` x have any different strictness than just plain x? I may be wrong, but I don't think so. Essentially, it's saying that when x is needed, evaluate x to WHNF and then return x. -- James ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Hi James,
On 20.09.2010, at 15:20, James Andrew Cook wrote:
Lazyness helps helps to reduce work if your input list is lazily constructed
and your function forces the returned element. Then you don't have to force
all elements of the list, only the last one. Let's say l = [e_0, ..., e_n].
All the e_i are expensive calculations.
g :: [a] - a
g xs = x `seq` x
where
x = head (reverse xs)
Can x `seq` x have any different strictness than just plain x? I may be
wrong, but I don't think so. Essentially, it's saying that when x is
needed, evaluate x to WHNF and then return x.
Yes, I think you are right. I was trying to force evaluation of the returned
element. Something like that:
{-# LANGUAGE BangPatterns #-}
g :: [a] - a
g xs = x
where
!x = head (reverse xs)
-- Jean___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On Monday 20 September 2010 15:20:53, James Andrew Cook wrote: On Sep 20, 2010, at 5:10 AM, Jean-Marie Gaillourdet wrote: Hi Alberto, On 20.09.2010, at 10:53, Alberto G. Corona wrote: 2010/9/18 Daniel Fischer daniel.is.fisc...@web.de n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). T No!. You forget laziness!. it is 0(n) with n= the parameter passed to n_lastn. It is not O(length list). the reversed and de-reversed elements are just the ones being taken , not the whole list. (please kill me if I´m wrong. I don´t want to live in a world where beauty is inneficient) I am afraid you are argumentation is wrong. Let's see: f :: [a] - a f = head . reverse This is a function running in O(n) time, where n is the length of given list. That is, because f has to follow at least n pointers in order to reach the end of the parameter list. It might be much more expensive if the list has to be computed, because f got only a thunk to cumpute a list instead of a finished list. I don't believe he was claiming O(n) time, only O(n) space, Right. which I am inclined to believe. Your 'f' should also run in O(1) space. Alas, no. At least with GHC (and I don't see how it could be otherwise), reverse is always an O(length xs) space operation. reverse :: [a] - [a] #ifdef USE_REPORT_PRELUDE reverse = foldl (flip (:)) [] #else reverse l = rev l [] where rev [] a = a rev (x:xs) a = rev xs (x:a) #endif Both, the report-reverse and the other version, build the reversed list as an accumulation parameter of a tail-recursive function. The entire reversed list is returned in one piece once the end is reached. The only way to make functions using reverse run in less than O(length xs) space is, as far as I know, using rewrite rules (e.g. head . reverse = last). In general, there can be no function depending in any way on the location of the end of the list that isn't O(length list) time, because if nothing else the end of the list must be discovered, which requires that much time no matter what the algorithm. Lazyness helps helps to reduce work if your input list is lazily constructed and your function forces the returned element. Then you don't have to force all elements of the list, only the last one. Let's say l = [e_0, ..., e_n]. All the e_i are expensive calculations. g :: [a] - a g xs = x `seq` x where x = head (reverse xs) Can x `seq` x have any different strictness than just plain x? No, x `seq` x is exactly equivalent to x. I may be wrong, but I don't think so. Essentially, it's saying that when x is needed, evaluate x to WHNF and then return x. Exactly. In x `seq` y, the seq forces evaluation of x to WHNF precisely if/when y has to be evaluated to WHNF. -- James ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
Have we put off the ultra-newbie by derailing his simple question into a discussion on subtle issues he shouldn't care about this early on? On Mon, Sep 20, 2010 at 3:49 PM, Daniel Fischer daniel.is.fisc...@web.dewrote: On Monday 20 September 2010 15:20:53, James Andrew Cook wrote: On Sep 20, 2010, at 5:10 AM, Jean-Marie Gaillourdet wrote: Hi Alberto, On 20.09.2010, at 10:53, Alberto G. Corona wrote: 2010/9/18 Daniel Fischer daniel.is.fisc...@web.de n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). T No!. You forget laziness!. it is 0(n) with n= the parameter passed to n_lastn. It is not O(length list). the reversed and de-reversed elements are just the ones being taken , not the whole list. (please kill me if I´m wrong. I don´t want to live in a world where beauty is inneficient) I am afraid you are argumentation is wrong. Let's see: f :: [a] - a f = head . reverse This is a function running in O(n) time, where n is the length of given list. That is, because f has to follow at least n pointers in order to reach the end of the parameter list. It might be much more expensive if the list has to be computed, because f got only a thunk to cumpute a list instead of a finished list. I don't believe he was claiming O(n) time, only O(n) space, Right. which I am inclined to believe. Your 'f' should also run in O(1) space. Alas, no. At least with GHC (and I don't see how it could be otherwise), reverse is always an O(length xs) space operation. reverse :: [a] - [a] #ifdef USE_REPORT_PRELUDE reverse = foldl (flip (:)) [] #else reverse l = rev l [] where rev [] a = a rev (x:xs) a = rev xs (x:a) #endif Both, the report-reverse and the other version, build the reversed list as an accumulation parameter of a tail-recursive function. The entire reversed list is returned in one piece once the end is reached. The only way to make functions using reverse run in less than O(length xs) space is, as far as I know, using rewrite rules (e.g. head . reverse = last). In general, there can be no function depending in any way on the location of the end of the list that isn't O(length list) time, because if nothing else the end of the list must be discovered, which requires that much time no matter what the algorithm. Lazyness helps helps to reduce work if your input list is lazily constructed and your function forces the returned element. Then you don't have to force all elements of the list, only the last one. Let's say l = [e_0, ..., e_n]. All the e_i are expensive calculations. g :: [a] - a g xs = x `seq` x where x = head (reverse xs) Can x `seq` x have any different strictness than just plain x? No, x `seq` x is exactly equivalent to x. I may be wrong, but I don't think so. Essentially, it's saying that when x is needed, evaluate x to WHNF and then return x. Exactly. In x `seq` y, the seq forces evaluation of x to WHNF precisely if/when y has to be evaluated to WHNF. -- James ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: text 0.9.0.0 and text-icu 0.4.0.0
On Sun, Sep 19, 2010 at 9:37 PM, John Millikin jmilli...@gmail.com wrote: What's new in text-0.9 ? All I see in darcs is a newtype'd param in the Foreign module. That is all that's new, but the PVP suggests that this requires a version bump, since it changes an existing interface. The purpose of the newtype is to make it less likely that one could confuse indices into the Word16 array with a count of Unicode code points. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On Sep 20, 2010, at 9:49 AM, Daniel Fischer wrote: which I am inclined to believe. Your 'f' should also run in O(1) space. Alas, no. At least with GHC (and I don't see how it could be otherwise), reverse is always an O(length xs) space operation. reverse :: [a] - [a] #ifdef USE_REPORT_PRELUDE reverse = foldl (flip (:)) [] #else reverse l = rev l [] where rev [] a = a rev (x:xs) a = rev xs (x:a) #endif Good point, I guess I hadn't really thought that one through. It should have occurred to me that the garbage collector has no idea what 'head' does, and so at the time that the list is forced to WHNF for matching in 'head', everything that reverse _could_ return must be retained, which is the whole list. I think I had a poorly-formed notion that the GC should somehow know that only the (eventual) head of the list would ever be needed. On Sep 20, 2010, at 10:22 AM, Daniel Peebles wrote: Have we put off the ultra-newbie by derailing his simple question into a discussion on subtle issues he shouldn't care about this early on? Probably. It's both a joy and a curse having a community so enthusiastic about their language. It's a lot like when people talk perl and everything somehow turns into code golf or just plain obfuscation contests ;) -- James___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: OpenGL Speed!
On 2010-09-18 13:57 +1000, Lie Ryan wrote: On 09/18/10 07:49, Mats Klingberg wrote: On Friday September 17 2010 19.53.01, Lie Ryan wrote: It depends. Updating 800x600 screen at 24-bit color 30 times per second requires 800*600*24*30 = 34560 bytes/s = 329 MB/s which is larger Shouldn't that be bits/s, or 800*600*3*30 = 41 MB/s? yep, blame that on lack of sleep, I guess... Nevertheless, 4x AGP (circa 2000) can easily sustain the significantly exaggerated rate of 329 MB/s. -- Nick Bowler, Elliptic Technologies (http://www.elliptictech.com/) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Re: Re: Re: Do expression definition
wren ng thornton wrote: On 9/17/10 4:04 PM, Ben Franksen wrote: wren ng thornton wrote: Note that when compilers do CPS conversion, everything is converted into let-binding and continuations (i.e., longjump/goto with value passing). It's just dual to the everything-is-lambda world, nothing special. Do you know a good online introduction to CPS conversion that explains the kind of duality you mentioned? Not off hand. These papers[1] give a pretty good explanation of CPS conversion and the other stages of compilation, from the perspective of proving compiler correctness. But they don't say much about the duality aspect of it. For the duality side of things, Andrzej Filinski's masters thesis[2] is an excellent read; though it doesn't say much about compilation IIRC. Thanks, I'll take a look. Basically the duality comes when decomposing a whole program. When we separate a term from its context, which part is in control? Control is just a perspective, so you could be outside the function looking in, or inside the function looking out. One person's push is another's pull. This is the same sort of thing as build/foldr vs unfoldr/destroy forms of list fusion: once we separate the F-algebra and F-coalgebra, which one should get the recursion?[3] Ok, this gives me some vague intuition. Cheers Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ultra-newbie Question
On Sep 18, 2010, at 7:51 PM, Christopher Tauss wrote: Hello Haskell Community - I am a professional programmer with 11 years experience, yet I just do not seem to be able to get the hang of even simple things in Haskell. I am trying to write a function that takes a list and returns the last n elements. There may be a function which I can just call that does that, but I am trying to roll my own just to understand the concept. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] Seems like it would be something like: n_lastn:: [a]-Int-[a] n_lastn 1 (xs) = last(xs) n_lastn n (x:xs) = The issue is I do not see how you can store the last elements of the list. Part of the reason why you may be having trouble is that you are thinking about things like how you can store the last elements of the list. I'm having trouble imagining what that might mean. Let's look at this in completely abstract terms. A list is a sequence. A (finite) sequence has a length, and there is a length function to find it. We can split a sequence into pieces, and there are take and drop functions to do it. We have these building blocks: length :: [t] - Int --length of sequence take :: Int - [t] - [t] --first n elements drop :: Int - [t] - [t] --all BUT the first n elements The only one of these that gives us a suffix of a list is 'drop'. So we are going to need n_lastn :: Int - [t] - [t] n_lastn count list = drop list What is the first argument of drop going to be? drop wants the number to DISCARD. You have the number to KEEP. The number to discard + the number to keep is the total length. So you will discard (length list - count) elements. And here we go with a complete answer: n_lastn count list = drop (length list - count) list This is a mathematical definition about (finite) sequences. We could write it and reason about it even if there had never been any such thing as a computer. It doesn't actually matter in the least HOW a list is stored; this definition will be RIGHT. Whether it is *efficient* does depend on how a list is stored. There are questions like - how often does the sequence have to be traversed (with lists, determining the length involves walking along the whole list until the end is found, although it does not involve looking at the elements) - how much copying is done (with arrays, you'd have to make a new array of count elements and copy the last count elements of list to it, with lists you don't have to copy anything) I can make this point another way. n_lastn is a bad name, because really, it's just the same as `take` except working from the other end. So we can define reverse_take n = reverse . take n . reverse reverse_drop n = reverse . drop n . reverse the last n items of a sequence are the first n items of its reversal, reversed all but the last n items of a sequence are all but the first n items of its reversal, reversed and your n_lastn is just reverse_take. This definition does three list traversals and two copies. There's a trick I found very useful in Prolog, and that is to exploit the homomorphism between lists and natural numbers, where a list can be used to represent its own length. Let's take `take` and `drop`. take (n+1) (x:xs) = x : take n xs take _ _ = [] drop (n+1) (_:xs) = drop n xs drop _ xs = xs Instead of passing a natural number as first argument, we'll pass a list, and the analogue of (n+1) is then (_:k). list_take, list_drop :: [any] - [t] - [t] list_take (_:k) (x:xs) = x : list_take k xs list_take _ _ = [] list_drop (_:k) (_:xs) = list_drop k xs list_drop _ xs = xs (drop count list) is a list, whose length is the number of elements we want to discard from the beginning of list. So we can define reverse_take count list = list_drop (drop count list) list and this does O(length list) work; ONE list traversal and NO copies. reverse_drop count list = list_take (drop count list) list This code was tested thus: *Main [reverse_take n abcd | n - [0..4]] [,d,cd,bcd,abcd] *Main [reverse_drop n abcd | n - [0..4]] [abcd,abc,ab,a,] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Ultra-newbie Question
On Sun, Sep 19, 2010 at 5:01 PM, Henrique Becker henriquebecke...@gmail.com wrote: Why not? import Data.Number.Nat as N lastN :: Integral b = b - [a] - [a] lastN n xs = N.drop (N.length xs - n') xs where n' = N.toNat n Wow. That is gorgeous! I think it's basically the same idea as my zipWith implementation, but it is so much clearer here. Thanks :-) Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Ultra-newbie Question
On Mon, Sep 20, 2010 at 5:11 PM, Luke Palmer lrpal...@gmail.com wrote: On Sun, Sep 19, 2010 at 5:01 PM, Henrique Becker henriquebecke...@gmail.com wrote: Why not? import Data.Number.Nat as N lastN :: Integral b = b - [a] - [a] lastN n xs = N.drop (N.length xs - n') xs where n' = N.toNat n Wow. That is gorgeous! I think it's basically the same idea as my zipWith implementation, but it is so much clearer here. Thanks :-) Er forget that zipWith comment. It is quite unlike that. But it is still beautiful and efficient. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Ultra-newbie Question
Thanks, It's my first post. If you not import Prelude is more clear (N. is horrible): import Prelude ((-), Integral) import Data.Number.Nat (drop, length, toNat) lastN :: Integral b = b - [a] - [a] lastN n xs = drop (length xs - n') xs where n' = toNat n P.S.: You benchmarked? I didn't... 2010/9/20, Luke Palmer lrpal...@gmail.com: On Mon, Sep 20, 2010 at 5:11 PM, Luke Palmer lrpal...@gmail.com wrote: On Sun, Sep 19, 2010 at 5:01 PM, Henrique Becker henriquebecke...@gmail.com wrote: Why not? import Data.Number.Nat as N lastN :: Integral b = b - [a] - [a] lastN n xs = N.drop (N.length xs - n') xs where n' = N.toNat n Wow. That is gorgeous! I think it's basically the same idea as my zipWith implementation, but it is so much clearer here. Thanks :-) Er forget that zipWith comment. It is quite unlike that. But it is still beautiful and efficient. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] [ANN] Crypto-API 0.1.0.0
Crypto-API is a project aimed at unifying algorithm developers and
users by presenting a uniform typeclass interface to low level
algorithms and providing generalized helper functions for the
(slightly) higher-level interactions needed by crypto-users. The main
features are typeclasses (hash, cipher, signing and RNG), block cipher
modes, platform independent entropy/seed acquisition, padding, testing
and benchmarking.
This release represents a fleshing out of the testing infrastructure,
addition of padding mechanisms, and a reduction in build dependencies.
In particular, I want to encourage package maintainers of TwoFish,
AES, and SHA* algorithms to use the included test infrastructure -
examples can be found on the homepage.
== Project Management ==
Homepage: http://trac.haskell.org/crypto-api/wiki
Bug trac: http://trac.haskell.org/crypto-api/report/1
Repo: http://code.haskell.org/crypto-api/
== API Removals ==
* Test.ParseNistKATs doesn't use Parsec and has a barebones interface.
* Crypto.Random does not export AsRG or Splittable (see change
log, 'random' build dep removed)
== API Additions ==
* class Signing p v | p - v, v - p where ...
* instance Monad (Either GenError) where ...
* cereal = 0.2 0.4 (was == 0.2.*)
* Testing
** Tests are split from Test.Crypto
** SHA, HMAC tests are new and from NIST CAVP KATs
** AES CFB128 mode KATs
** TwoFish NIST KATs
** Cipher property tests included (enc . dec ~ id, and many mode
specific tests)
* Crypto.Padding is included with PKCS5 and ESP padding methods.
* blockSizeBytes helper function is now included
== Build Dependencies ==
While I've never had objections to dependencies (this is what cabal is
for and removing unused code is what GHC+linkers are for), I feel this
is a good minimum and hope others agree. Some potential users made
noise about having both Binary and Cereal and just the number of deps
in general.
* deps removed: binary, parsec, random (and indirectly: time, old-locale)
* deps remaining: base, tagged, bytestring, cereal, filepath, directory
* indirect deps remaining: data-default, containers, arrays
To reiterate, the only deps above a normal GHC baseline are tagged,
cereal, and data-default.
CHANGE LOG (since 0.0.0.2)
* Add 'Signing' class.
* Tests showing the strict and lazy Crypto.Modes functions are eq
* Basic BlockCipher property tests (enc . dec ~ id)
* Enable tests for CFB128
* Added ESP and PCKS5 padding
* add a 'blockSizeBytes' helper
* TwoFish KATs
* Bump 'cereal' version bound to include 0.3
* instance Monad (Either GenError) -- that was an obvious oversight
* Remove the 'binary' dep. (cereal makes more sense and can be
leveraged in Binary.{Get,Put} routines).
* Removed the 'parsec' dep, which was only needed for Test.* but not
even that now.
* Updated the CPP tests for Windows in System.Random.Crypto (still
need a tester)
* Fixed up the testing infrastructure. Algorithms now use separate
modules (Test.SHA, Test.HMAC, Test.AES). more NIST KATs included:
~1000 SHA tests, hundreds of SHA HMAC tests.
* Fixed ugly bug for HMACs using keys blockSize (eep! Obvious
interop problem, but there was no-less security in the hmac result)
* Removes the 'random' dep and by extension removes indirect deps on
time and old-locale. Random was only used to provide trivial lifting
of a newtype wrapped CryptoRandomGen instances into the RandomGen
class, which was of questionable sense in the first place.
== TODO ==
* Improve benchmarking infrastructure
** Improved reporting
** Benchmark modes and other higher-level functions, but in a generic way
** Benchmark asymmetric algorithms
* Optimize block cipher modes
* Statistical RNG tests
* Portability testing (Mac, Windows testing needed)
Cheers,
Thomas
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: ieee version 0.7
On Mon, Sep 20, 2010 at 03:22, Daniel Fischer daniel.is.fisc...@web.de wrote: unsafeCoerce is not supposed to work for casts between Integral and Floating types. If you try to unsafeCoerce# between unboxed types, say Double# and Word64#, you're likely to get a compile failure (ghc panic). If you unsafeCoerce between the boxed types, it will probably work, but there are no guarantees. There's a feature request for unboxed coercion (i.e. reinterpretation of the bit-pattern): http://hackage.haskell.org/trac/ghc/ticket/4092 Interesting -- in that bug report, Simon Mar says that converting the value using pointers will work correctly. I've changed d-b-ieee754 over to use this method (v 0.4.2); the tests are still passing, so I'll call it success. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: ieee version 0.7
On 21 September 2010 12:18, John Millikin jmilli...@gmail.com wrote: On Mon, Sep 20, 2010 at 03:22, Daniel Fischer daniel.is.fisc...@web.de wrote: unsafeCoerce is not supposed to work for casts between Integral and Floating types. If you try to unsafeCoerce# between unboxed types, say Double# and Word64#, you're likely to get a compile failure (ghc panic). If you unsafeCoerce between the boxed types, it will probably work, but there are no guarantees. There's a feature request for unboxed coercion (i.e. reinterpretation of the bit-pattern): http://hackage.haskell.org/trac/ghc/ticket/4092 Interesting -- in that bug report, Simon Mar says that converting the value using pointers will work correctly. I've changed d-b-ieee754 over to use this method (v 0.4.2); the tests are still passing, so I'll call it success. I've been using unsafeCoerce: getFloat64be :: Get Double getFloat64be = do n - getWord64be return (unsafeCoerce n :: Double) putFloat64be :: Double - Put putFloat64be n = putWord64be (unsafeCoerce n :: Word64) but only tested it with quickcheck -- it passes about 10^7 checks, comparing roundtrips in combinatrion with the previous data-binary-ieee754 versions. However could that sometimes behave incorrectly? Should the d-b-iee754-0.4.2 versions with castPtr etc. be even faster? Conrad. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
