[Haskell-cafe] head as a total function
Jo'n Fairbairn wrote in response to Neil Mitchell: And as you go on to say, if you apply it to the infinite list, who cares if you used head. Head is only unsafe on an empty list. So the problem then becomes can you detect unsafe calls to head and let the programmer know. No, that's the wrong approach because it relies on detecting something that (a) the programmer probably knows already and (b) is undecidable in general. It would be far better for the programmer to express this knowledge in the programme. It is indeed possible -- and quite easy -- to write programs where head and tail are total functions. That issue was discussed, for example, at the end of an old message: Exceptions in types and exception-free programming http://www.haskell.org/pipermail/haskell/2004-June/014271.html The first two thirds of the message showed how to make exceptions apparent in the signature of a function, so we can see if a function could potentially raise the `head of an empty list' exception just by looking at its (inferred) type. The exception-free programming is far more rewarding, and practical as well. We don't actually need to introduce subtyping; explicit injection/projections don't seem to be as much of (syntactic) overhead. There is absolutely no runtime overhead! The non-empty lists have exactly the same run-time representation as the regular lists. The technique generalizes to arrays, even numbers, sorted lists (and, seemingly, to strings that are safe to include into HTML/SQL documents). That technique has been mentioned several times recently (perhaps not on this forum). Quite complex algorithms like Knuth-Morris-Pratt string search (with mutable arrays, packed strings, general recursion and creative index expressions) can be handled. Again, without introducing any runtime overhead: http://pobox.com/~oleg/ftp/Haskell/KMP-deptype.hs The approach is formalizable; the recent PLPV talk by Chung-chieh Shan presented the types systems and the proof techniques. Some of the proofs have been formalized in Twelf: http://pobox.com/~oleg/ftp/Computation/lightweight-dependent-typing.html#Formalization In short, the safety property (absence of `head of an empty list' exception) is a corollary to the Progress theorem, for a type system with dependent-type flavor. The type system doesn't actually have dependent types. Furthermore, whatever dependent-type flavor there is, it can be erased while maintaining the safety guarantees, given some precisely stated conditions on the safety kernel. P.S. Algol68 was my favorite language too. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Reading integers
Hello Neil, Thursday, September 7, 2006, 1:45:03 AM, you wrote: Currently I have a single module that provides reading operations for Integers and Ints. I'm not quite sure what to do with it. Get it into base! Where it is, or what its called is less relevant - perhaps entirely decoupled from the Read class, and I wouldn't have thought reading octal integers etc was useful - just simple bog standard integers. I'd really like just readInt/readInteger in Numeric, or Prelude, or possibly even a new Read style module. i'd just defined the following function, mainly because standard 'read' machinery occupies whole 50 kb in exe-file readI = foldl f 0 where f m c | isDigit c = fromIntegral (ord c - ord '0') + (m * 10) | otherwise = error (Non-digit ++[c]++ in readI) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] head as a total function
Hello oleg, Thursday, September 7, 2006, 10:28:00 AM, you wrote: P.S. Algol68 was my favorite language too. +1 :) it was the first imperative language supporting closures, after all -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how do you debug programs?
On Wed, Sep 06, 2006 at 11:34:05AM +0200, Pepe Iborra wrote: Hi Tamas There are several ways to debug a Haskell program. The most advanced ones are based in offline analysis of traces, I think Hat [1] is the most up-to-date tool for this. There is a Windows port of Hat at [5]. Another approach is to simply use Debug.Trace. A more powerful alternative for this approach is Hood [2]. Even if it hasn't been updated in some time, Hood works perfectly with the current ghc distribution. Even more, Hugs has it already integrated [3]. You can simply import Observe and use observations directly in your program. Dear Pepe, Thank you for the information. I finally ended up working with Debug.Trace, and found the bug very quickly. I also tried Hood, but couldn't load it in ghci: import Observe can't find the library, but % locate Observe /usr/lib/ghc-6.4.2/hslibs-imports/util/Observe.hi /usr/lib/ghc-6.4.2/hslibs-imports/util/Observe.p_hi /usr/lib/hugs/libraries/Hugs/Observe.hs /usr/lib/hugs/oldlib/Observe.hs Does importing from hslibs-imports require something special? Quite a bit of philosophical discussion erupted as a result of my original question. I understand the arguments of those who dislike debuggers, but I don't think I could have done without some debugging. It turns out that the problem was not in the algorithm, but in the specification of the equation itself. I was solving a continuous time Hamilton-Jacobi-Bellman equation, and there was a point in the state space where the supremum was infinity, giving stuff like 0/Inf and their ilk. I respecified the problem and now it works. For those who think that it is always possible to break the problem up into small pieces you can test individually (without a debugger): you can't, at least not when solving functional equations. The corner cases (and nonconvergence, when using non-contraction methods, such as PEA) are difficult to catch and reproduce. Thanks for all the suggestions, Tamas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] NaN, Infinity literals
You want the RealFloat class functions: http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t%3ARealFloat Tamas K Papp wrote: Hi, Is there a way to use NaN and Infinity as literals, or at least to test if a value is NaN or Infinity? I tried *Main let nan=0/0 *Main nan NaN *Main nan==0/0 False so storing the value does not work... Thanks, Tamas ___ 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] NaN, Infinity literals
Hi, Tamas K Papp wrote: Is there a way to use NaN and Infinity as literals, or at least to test if a value is NaN or Infinity? *Main let nan=0/0 *Main nan NaN *Main nan==0/0 False This is correct according to the IEEE 754 standard, which defines that NaN compares unequal to everything, including itself. You can test the numbers using the isNaN and isInfinite functions. Incidentally, one can define isNaN x = x /= x for IEEE floating point numbers. Comparing with +Infinity and -Infinity works as expected. regards, Bertram. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] NaN, Infinity literals
Tamas K Papp wrote: Is there a way to use NaN and Infinity as literals, or at least to test if a value is NaN or Infinity? *Main let nan=0/0 *Main nan NaN *Main nan==0/0 False so storing the value does not work... Not sure what you mean here. In IEEE floating point, NaN is not equal to anything, especially not to itself. So the above worked, didn't it? And therefore, isNaN :: Double - Bool isNaN x = not (x == x) but this is wrong (I believe): isNaN' :: Double - Bool isNaN' x = x /= x Anyway, isNaN is alerady in the Prelude, and so are isInfinite, isDenormalized and isNegativeZero. This is all a bit ill-defined, but you'll have to live with that. If you also want a personal advise: switch on signaling NaNs (there's a C function to do that, simply foreign import it) and have your program bomb out as soon as a NaN is formed. Propagating them through calculations just increases the headache. Udo. -- FORTUNE PROVIDES QUESTIONS FOR THE GREAT ANSWERS: #4 A: Go west, young man, go west! Q: What do wabbits do when they get tiwed of wunning awound? signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad laws
Deokhwan Kim wrote: What is the practical meaning of monad laws? (M, return, =) is not qualified as a category-theoretical monad, if the following laws are not satisfied: 1. (return x) = f == f x 2. m = return == m 3. (m = f) = g == m (\x - f x = g) But what practical problems can unsatisfying them cause? In other words, I wonder if declaring a instance of the Monad class but not checking it for monad laws may cause any problems, except for not being qualified as a theoretical monad? Afaiu the monad laws are needed so the compiler can do various optimizations, especially in regard to the do notation. Consider: g c = do if c then p else return () q Intuitively, the else branch of the if statement does nothing interesting, but we need to put something there because we can't just leave the branch empty, hence the use of (return ()), but thankfully, because of the monad laws, the compiler can apply transformations to get rid of it when it desugars the do notation. The above is equivalent to: g c = (if c then p else return ()) = (\_ - q) which could be re-written as: g c = if c then (p = (\_ - q)) else (return () = (\_ - q)) which can be optimized using monad law 1) to: g c = if c then (p = (\_ - q)) else (\_ - q) () which can further be optimized to: g c = if c then (p = (\_ - q)) else q so when the condition (c) is False we don't waste time doing the (return ()) action, but go straight to (q). However if your monad didn't satisfy the laws, the compiler would still assume that it did thus leading to a flawed optimization ie the compiler would throw your program away and substitute it for a different, unrelated, program... Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Reading integers
What about negative numbers? Also, don't use (ord c - ord '0'), it doesn't work with Unicode digits. That's why there is a digitToInt function. -- Lennart On Sep 7, 2006, at 02:12 , Bulat Ziganshin wrote: readI = foldl f 0 where f m c | isDigit c = fromIntegral (ord c - ord '0') + (m * 10) | otherwise = error (Non-digit ++[c]++ in readI) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: how do you debug programs?
thinking helps, but claiming that tools can't help doesn't. Lets be absolutely clear about this: I've never claimed that tools can't help. In this thread I've been using the term debugger in the narrow sense implied by the OP's question -- something that steps through the execution of the code. Such a debugger is inappropriate for Haskell programmers, and doubly so for beginners. well, then it is clear that we disagree on this. imho, being able to step through reductions is very appropriate for all functional programmers (**), and an essential exercise for beginners. and if that is true for tiny examples on paper, then there should be tool support for applying it to larger programs. from experience with the PI-RED systems, there are few cases where one can apply such a tool without thinking (eg. let it run till it gets stuck on an error, go a few steps back to see where that erroneous part was constructed; or let it run for a large number of steps, then check why and where the program it is still growing instead of terminating). (*) after the initial learning phase, where such a stepper helps to form the student's mental model of program evaluation, the majority of debugging cases need to combine thinking with experimentation, but dropping either of these two ingredients makes the problem much harder. and it is nice to be able to do the experiments without having to switch tools or mindsets (although there are many ways in which the old PI-RED systems could have been improved, not to mention lessons learned from other tools, like Hat, that were developed for Haskell because there were no reduction systems for it). claus (*) note that the programmer never saw thunks, or stacks, let alone heap objects or abstract machine code, only high-level program text, transformed by reductions. intermediate programs were fully editable, in no way distinguished from the original programs entered by the programmer, so one could make some local observations, changes and reductions, then continue with the overall reduction, or return to the original program. compilation, decompilation, and presentation were implicit, under the hood. for the PI-RED developers, though, there were *separate* debugging tools that would allow them to inspect the abstract machine's stack, heap, etc.. and only if those failed to indicate the problem, would they have to resort to C-level debugging tools, another level lower. (**) in fact, Berkling used to argue that was true for all declarative programmers, and he extended his ideas and machines to functional logic languages ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad laws
Brian, Are you really sure Haskell compilers do that optimization? I would regard a compiler that does optimizations that are justified by laws that the compiler cannot check as broken. -- Lennart On Sep 7, 2006, at 08:50 , Brian Hulley wrote: Deokhwan Kim wrote: What is the practical meaning of monad laws? (M, return, =) is not qualified as a category-theoretical monad, if the following laws are not satisfied: 1. (return x) = f == f x 2. m = return == m 3. (m = f) = g == m (\x - f x = g) But what practical problems can unsatisfying them cause? In other words, I wonder if declaring a instance of the Monad class but not checking it for monad laws may cause any problems, except for not being qualified as a theoretical monad? Afaiu the monad laws are needed so the compiler can do various optimizations, especially in regard to the do notation. Consider: g c = do if c then p else return () q Intuitively, the else branch of the if statement does nothing interesting, but we need to put something there because we can't just leave the branch empty, hence the use of (return ()), but thankfully, because of the monad laws, the compiler can apply transformations to get rid of it when it desugars the do notation. The above is equivalent to: g c = (if c then p else return ()) = (\_ - q) which could be re-written as: g c = if c then (p = (\_ - q)) else (return () = (\_ - q)) which can be optimized using monad law 1) to: g c = if c then (p = (\_ - q)) else (\_ - q) () which can further be optimized to: g c = if c then (p = (\_ - q)) else q so when the condition (c) is False we don't waste time doing the (return ()) action, but go straight to (q). However if your monad didn't satisfy the laws, the compiler would still assume that it did thus leading to a flawed optimization ie the compiler would throw your program away and substitute it for a different, unrelated, program... Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ 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] Monad laws
On Sep 7, 2006, at 9:04 AM, Lennart Augustsson wrote: Brian, Are you really sure Haskell compilers do that optimization? I would regard a compiler that does optimizations that are justified by laws that the compiler cannot check as broken. What, like list fusion? ;-) Although, more seriously, there are a number of monads in the standard libs that don't follow the monad laws (including IO http:// article.gmane.org/gmane.comp.lang.haskell.general/5273 !!). I can't imagine that any haskell compilers rely on these laws to do program transformations. -- Lennart On Sep 7, 2006, at 08:50 , Brian Hulley wrote: Deokhwan Kim wrote: What is the practical meaning of monad laws? (M, return, =) is not qualified as a category-theoretical monad, if the following laws are not satisfied: 1. (return x) = f == f x 2. m = return == m 3. (m = f) = g == m (\x - f x = g) But what practical problems can unsatisfying them cause? In other words, I wonder if declaring a instance of the Monad class but not checking it for monad laws may cause any problems, except for not being qualified as a theoretical monad? Afaiu the monad laws are needed so the compiler can do various optimizations, especially in regard to the do notation. Consider: g c = do if c then p else return () q Intuitively, the else branch of the if statement does nothing interesting, but we need to put something there because we can't just leave the branch empty, hence the use of (return ()), but thankfully, because of the monad laws, the compiler can apply transformations to get rid of it when it desugars the do notation. The above is equivalent to: g c = (if c then p else return ()) = (\_ - q) which could be re-written as: g c = if c then (p = (\_ - q)) else (return () = (\_ - q)) which can be optimized using monad law 1) to: g c = if c then (p = (\_ - q)) else (\_ - q) () which can further be optimized to: g c = if c then (p = (\_ - q)) else q so when the condition (c) is False we don't waste time doing the (return ()) action, but go straight to (q). However if your monad didn't satisfy the laws, the compiler would still assume that it did thus leading to a flawed optimization ie the compiler would throw your program away and substitute it for a different, unrelated, program... Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: how do you debug programs?
On Thu, Sep 07, 2006 at 06:21:01AM +0100, Jn Fairbairn wrote: David Roundy [EMAIL PROTECTED] writes: On Wed, Sep 06, 2006 at 09:56:17AM -0700, Jason Dagit wrote: Or maybe even more extreme you could use template haskell or the c preprocessor to fill in the line number + column. Which is precisely what darcs does for fromJust (which we use a lot): we define a C preprocessor macro fromJust. Curiously, the only bug in darcs that has bitten me so far was a use of fromJust. Perhaps that indicates a weakness in the style, rather than the tools? Yeah, in general fromJust is a dangerous business, and most of the uses of it in darcs can lead to trouble for partial repositories, for instance. I was just yesterday discussing with Jason the possibility of switching away from a Maybe approach for lazily reading patches. -- David Roundy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Reading integers
Lennart Augustsson wrote: Also, don't use (ord c - ord '0'), it doesn't work with Unicode digits. That's why there is a digitToInt function. FWIW, in Haskell 98, isDigit and digitToInt are defined as isDigit c= c = '0' c = '9' digitToInt :: Char - Int digitToInt c | isDigit c= fromEnum c - fromEnum '0' | c = 'a' c = 'f' = fromEnum c - fromEnum 'a' + 10 | c = 'A' c = 'F' = fromEnum c - fromEnum 'A' + 10 | otherwise= error Char.digitToInt: not a digit making this a bit of a red herring. I can't comment on why Bulat doesn't like negative numbers. Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how do you debug programs?
On 07/09/2006, at 10:53, Tamas K Papp wrote: Dear Pepe, Thank you for the information. I finally ended up working with Debug.Trace, and found the bug very quickly. I also tried Hood, but couldn't load it in ghci: import Observe can't find the library, but % locate Observe /usr/lib/ghc-6.4.2/hslibs-imports/util/Observe.hi /usr/lib/ghc-6.4.2/hslibs-imports/util/Observe.p_hi /usr/lib/hugs/libraries/Hugs/Observe.hs /usr/lib/hugs/oldlib/Observe.hs Does importing from hslibs-imports require something special? Hi Tamas I'm glad to hear that you fixed it! GHC includes Observe (the hs-libs-imports file you are seeing) only in the hidden 'util' package, which I believe is deprecated or not present in 6.6. If you want to use it, launch ghci with the flag '- package util'. Or download Observe.hs from the Hood website and place it somewhere in the path. Hmm, it would be handy to have a Cabal Hood package... Cheers pepe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad laws
Lennart Augustsson wrote:
On Sep 7, 2006, at 08:50 , Brian Hulley wrote:
Deokhwan Kim wrote:
What is the practical meaning of monad laws?
Afaiu the monad laws are needed so the compiler can do various
optimizations, especially in regard to the do notation. Consider:
g c = do
if c
then p
else return ()
q
which can further be optimized to:
g c = if c then (p = (\_ - q)) else q
Brian,
Are you really sure Haskell compilers do that optimization?
I would regard a compiler that does optimizations that are justified
by laws that the compiler cannot check as broken.
I think at least GHC does, if I understand the -ddump-simpl output below
properly:
-- in Monad.hs
module Main where
import Control.Monad
test :: Bool - IO ()
test c = do
if c
then putStr True
else return ()
putStrLn Finish
main = test False
ghc --make -O2 -ddump-simpl monad
gives:
Tidy Core
Main.s :: GHC.Base.String
[GlobalId]
[Str: DmdType]
Main.s = GHC.Base.unpackCString# Finish
Main.main :: GHC.IOBase.IO ()
[GlobalId]
[Arity 1
Str: DmdType L]
Main.main = \ (eta_a26L :: GHC.Prim.State# GHC.Prim.RealWorld) -
case (# GHC.Prim.State# GHC.Prim.RealWorld, () #) GHC.IO.hPutStr
GHC.Handle.stdout Main.s eta_a26L
of wild_a26O { (# new_s_a26M, a85_a26N #) -
System.IO.lvl1 new_s_a26M
}
Main.s1 :: GHC.Base.String
[GlobalId]
[Str: DmdType]
Main.s1 = GHC.Base.unpackCString# True
Main.test :: GHC.Base.Bool - GHC.IOBase.IO ()
[GlobalId]
[Arity 2
Str: DmdType SL]
Main.test = \ (c_a19p :: GHC.Base.Bool)
(eta_s27s :: GHC.Prim.State# GHC.Prim.RealWorld) -
case (# GHC.Prim.State# GHC.Prim.RealWorld, () #) c_a19p of wild_B1 {
GHC.Base.False - Main.main eta_s27s;
GHC.Base.True -
case (# GHC.Prim.State# GHC.Prim.RealWorld, () #) GHC.IO.hPutStr
GHC.Handle.stdout Main.s1 eta_s27s
of wild1_a27o { (# new_s_a27m, a85_a27n #) -
Main.main new_s_a27m
}
}
So when the condition in Main.test is False, the compiler immediately
executes Main.main eta_s27s which does the putStr Finish directly, so the
return () has been optimized out.
Whether this is because ghc has used the monad laws, or has applied some
different optimization due to it's knowledge of the built-in IO monad etc I
don't know.
Even if the compiler is not itself making use of the laws, other parts of
standard library code might be, and their correctness would therefore also
depend on something which the compiler can't verify.
It seems a pity that having gone to the trouble of ensuring a monad obeys
the laws, the compiler can't make use of them. What then *is* the point of
the monad laws?
Regards, Brian.
--
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.
http://www.metamilk.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Monad laws
Are you really sure Haskell compilers do that optimization? I would regard a compiler that does optimizations that are justified by laws that the compiler cannot check as broken. You mean like the non-aliasing law in Fortran? Stefan ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[4]: [Haskell-cafe] Reading integers
Hello Bertram, Thursday, September 7, 2006, 6:01:17 PM, you wrote: Also, don't use (ord c - ord '0'), it doesn't work with Unicode digits. That's why there is a digitToInt function. making this a bit of a red herring. I can't comment on why Bulat doesn't like negative numbers. because my program can't split files into chunks of -10 files or -1 mbytes ;) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] head as a total function
On Thu, 2006-09-07 at 11:03 +0400, Bulat Ziganshin wrote: . . . it was the first imperative language supporting closures, after all Uh, what about lisp? The (MIT) lisp 1.4 manual (ca. 1965) refers to FUNCTION differing from QUOTE in that it handled free variables correctly; I take this to mean that at least a primitive form of closure was provided. Moreover, a language that provides SET/SETQ, RPLACA/RPLACD and the PROG feature (including labels and a goto) surely qualifies as imperative? -- Bill Wood ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Reading integers
Hi, I've implemented replacements for readsPrec for Int and Integer in a module called Compat (in my darcs repository [1]) and measured their performance. There's some overhead when compared to the plain versions. For Integer, it's about 30% for single digit numbers, going down to about 10% at 10 digits, and about 1.3% at 100. It's still a big win over the existing instances at a small loss in compatibility to Haskell 98. As far as I can make out, the only difference is that it fails to diverge in some cases where reads would diverge (see my initial mail for an example.) I've also received a question from Ketil Malde off list, asking (in reply to Neil Mitchell) what the advantages would be of having this in base. Personally I think it should go into base if we can agree on replacing existing code (the Read instances or something in Numeric or maybe both). This would have the advantage of making quite a few programs more efficient just by recompiling them. If we can't agree on that, the code will be made available as an extra module but I wouldn't see any advantage at having it in base. Having it distributed with ghc would have some advantages (mainly convenience for users and a slightly better chance of avoiding forks). In other news, darcs send will now send the patches to me - in case anyone has any. regards, Bertram [1] I'll say again that browsing directly doesn't work, darcs is fine though, get the code with darcs get http://int-e.home.tlink.de/haskell/readinteger ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Reading integers
Bertram Felgenhauer wrote: I can't comment on why Bulat doesn't like negative numbers. Neither it seems, did the original Haskell committee - that's why we have to muddle along with a confusing unary minus operator instead of proper negative literals - see the thread beginning http://www.haskell.org/pipermail/haskell-cafe/2006-August/017410.html for the latest exciting attempt to get rid of unary minus... ;-) Regards, Brian. -- Man simply could not have the right interest in beauty if in his life of soul he were not entangled in a world of hideously ugly spider-like beings. - Rudolf Steiner 16/12/1922 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] head as a total function
it was the first imperative language supporting closures, after all Uh, what about lisp? For those who read the Foozles slides posted earlier [0], I must say he nailed this one, on slide 2. The (MIT) lisp 1.4 manual (ca. 1965) refers to FUNCTION differing from QUOTE in that it handled free variables correctly; I take this to mean that at least a primitive form of closure was provided. Steele's work on Scheme helped Lisp programmers take lexical scoping seriously [1]; these ideas and a method for efficient implementation were attributed to Algol [2]. That lexical scope was available in some dialect of Lisp, even very early on, doesn't surprise me (and according to [3] is the case). But I do think dynamic scoping took a while to die out as generally accepted Lisp practice (it does still exist in Common LISP, with a special keyword, IIRC) and that Scheme (late 1970s) helped to effect that. Moreover, a language that provides SET/SETQ, RPLACA/RPLACD and the PROG feature (including labels and a goto) surely qualifies as imperative? Haskell has been called the best imperative programming language ever. :-) I mean, Haskell has IORef and friends, right? Jared. [0] http://hope.cs.rice.edu/twiki/pub/WG211/M3Schedule/foozles.pdf [1] Tenth paragraph, this page: http://www.lisp.org/table/Lisp-History.html [2] Steele's Rabbit compiler paper, p.13. See also Steele's Lambda papers [3] Steele and Gabriel, Evolution of Lisp. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] map (-2) [1..5]
On 17/08/06, Brian Hulley [EMAIL PROTECTED] wrote: Jared Updike wrote: In other words, superscripts bind tighter than prefix ops but prefix ops bind tighter than infix. I see. My point is that there already exists a convention[1] that the way to type in 2 -4 is -4^2 which means -(4^2) not (-4)^2 because - as a prefix op has the same precedence as binary subtraction, not super tight like normal prefix ops (i.e. normal function application) as you would like it to be (if I understand correctly). You are welcome to break an existing (unofficial) convention for the sake of lexical syntax[2]. [2] http://wadler.blogspot.com/2006/01/bikeshed-coloring.html This choice of precedence for unary - conflicts with the normal usage in languages like C, where unary ops obviously bind tighter than infix. The typesetting in maths conveys a lot of info eg to distinguish f -x from f - x or f-x, and so the relationship between the visual representation and the meaning depends on a knowledge of various conventions that have evolved over time, and the knowledge of when to apply them in a given context. In contrast, a programming language should be based on general concepts uniformly applied. In Haskell we have operators, identifiers, prefix application using an identifier and infix application using a symbol, and a uniform way to convert a symbol to an identifier and vice versa, and a uniform way of forming sections. All this machinery should be enough to be satisfied with. However, someone somewhere decided that one trivial arithmetic operation, namely unary minus, should be allowed to totally ruin everything, and not only that, but that half of any number line, the positives, should (literally!) have a special advantage over the other half, the negatives. Thus while I can agree with Wadler that it's easy to have different opinions on little issues, I think that in this case the goal of uniformity leads to an objective answer. Of course not all languages care about being uniform or neat ;-) Best regards, Brian. First, f - x, f -x, and f-x all tend to mean the same thing in mathematics, though f -x would be considered poorly typeset (and, to some degree, they're all poorly typeset, because we're using hyphens rather than the minus symbol, which really don't look the same). We tend to write f(-x) when applying a function f to the negation of x, even in circumstances when application is normally written without parentheses. Secondly, I think it's quite a reasonable thing to do to treat unary negation as a separate operation. It follows quite naturally to do so from the definition of a ring. While having separate literals for negative numbers might be okay, it seems unnecessary in light of the fact that we *do* want a nice looking unary negation symbol, which doesn't strictly apply to literals. If -x suddenly became a non-expression, and I had to write 0-x, -1*x or (negate x) instead, I'd consider that a severe enough bug that I would avoid upgrading my compiler until it was fixed. In mathematics, we don't use separate symbols for negative integers, and negated positive integers, even though in the underlying representation of the integers as equivalence classes of pairs of naturals, we can write things like -[(1,0)] = [(0,1)], which expressed in ordinary notation just says that -1 = -1. This doesn't bother us, because the two things are always equal. Another thing to note is that all the natural literals are not, as one might initially think, plain values, but actually represent the embedding of that natural number into the ring (instance of Num), by way of 0 and 1. They simply provide a convenient notation for getting particular values of many rings, but in many cases, don't get one very far at all before other functions must be introduced to construct the constant values one wants. While there always is a homomorphism from Z to a ring (represented in Haskell by fromInteger), one would get similar expressiveness by with just the nullary operators 0 and 1, and the unary negation as well as addition and multiplication (albeit with an often severe performance hit, and some annoyance, I'm not recommending we really do this, simply characterising the purpose of numeric literals). If the performance issue regarding the polymorphic literal -5 meaning negate (fromInteger 5) is a problem, it would be easy enough to agree for the compiler to find and rewrite literals like that as fromInteger (-5) instead, where -5 is the precomputed integer -5. Assuming that fromInteger is not broken, that will always mean the same thing (because fromInteger is supposed to be a homomorphism). Similarly, when the type of (fromInteger x) is known statically to be Integer, the compiler can rewrite it as x. In any event, this is a tiny constant factor performance hit. Anyway, the point of all this is that 0,1,2... are not really literals at all. They're nullary operators which give particular elements of any given
Re: [Haskell-cafe] Monad laws
G'day all. Quoting Deokhwan Kim [EMAIL PROTECTED]: What is the practical meaning of monad laws? Interesting philosophical question. There will be an article on this topic in the next The Monad.Reader, so watch this space. But what practical problems can unsatisfying them cause? Pretty much the same as any practical problems that occur when you break invariants. What problems do you cause if you don't maintain your binary search trees in sorted order, for example? Basically, you break anything which depends on the laws. For example, breaking any of the monad laws implies breaking the functor laws (exercise: prove this), so fmap breaks. Monad transformers may depend on the underlying monad to satisfy the laws, so you break stacked transformers. Using non-conforming monads as Kleisli arrows break the arrow laws. Any and all of this may result in programs which misbehave. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] head as a total function
Hello Bill, Thursday, September 7, 2006, 8:24:53 PM, you wrote: it was the first imperative language supporting closures, after all Uh, what about lisp? Lots of Idiotic Silly Parentheses? :) well, i say about more or less well-known non-FP languages. actually, i'm sure that some FBCPL supports closures (or at least anonymous functions) several years before Algol-68 :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
