Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Re: lazyness and tail recursion (Ovidiu Deac) 2. cabal check complains about missing Setup.hs (Ovidiu Deac) 3. Re: cabal check complains about missing Setup.hs (Daniel Fischer) 4. Re: cabal check complains about missing Setup.hs (Ovidiu Deac) 5. question on types (Jake Penton) 6. Re: question on types (Brandon Allbery) 7. Re: question on types (Julian Porter) ---------------------------------------------------------------------- Message: 1 Date: Thu, 28 Jul 2011 13:27:44 +0300 From: Ovidiu Deac <ovidiud...@gmail.com> Subject: Re: [Haskell-beginners] lazyness and tail recursion To: Will Ness <will_...@yahoo.com> Cc: beginners@haskell.org Message-ID: <CAKVsE7viO23K_Jn4=jspwantl2c4jfg1ev10qy1km171ucg...@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 If I got it right, the idea is to keep the number of operations between the recursive call and the end of the function constant. On Wed, Jul 27, 2011 at 1:38 AM, Will Ness <will_...@yahoo.com> wrote: > Ovidiu Deac <ovidiudeac <at> gmail.com> writes: > >> >> I've read the paragraph below from Real World Haskell >> > (http://book.realworldhaskell.org/read/efficient-file-processing-regular-expressions-and-file-name-matching.html >> section "An important aside: writing lazy functions") >> >> I can get a feeling why lazyness compensates for the lack of tail >> recursion but I don't really understand why it would work in general. >> >> My understanding is that that a function which returns a list with >> non-tail recursion would only work this way with certain usage >> patterns. In this case the caller of the funtion will have to use the >> string in a stream-like fashion. > > The concept of tail recursion modulo cons is similar. Wikipedia has an > article. > Basically it's about keeping one execution frame above the tail-recursive one. > Lazily accessing a list from the top is a lot like adding elements to it one > by > one at the bottom. Prefixing a recursive call with an operation of fixed > number > of operations is OK, because they will get consumed and the recursive case > called, in a fixed number of steps - the instance between current point and > next > recursive invocation point won't grow, only get increased at times by a set > amount and then get consumed. > > The problem with non-tail recursion in lazy setting is that the distance grows > between the current point and the next invocation, and so the amount of "what > to > do next?" information grows all the time. In imperative setting it gets > flipped > into "what to do after the invocation" but it still grows. In tail-recursion > (even modulo cons, or (++) with fixed prefix) it's bounded, finite, constant. > Looking at Scheme example code in WP "continuation-passing style" article > might > help. There we see as in translations of tail-recursive functions the > constructed continuation does not grow in unlimited fashion, instead only > maybe > getting prefixed by a fixed amount of operations at times. > > Does it make any sense? :) > > > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://www.haskell.org/mailman/listinfo/beginners > ------------------------------ Message: 2 Date: Thu, 28 Jul 2011 15:17:04 +0300 From: Ovidiu Deac <ovidiud...@gmail.com> Subject: [Haskell-beginners] cabal check complains about missing Setup.hs To: beginners <beginners@haskell.org> Message-ID: <CAKVsE7uR0AX2DV+ugqEMc=uzgmzsej0zrmst83t6nevao2j...@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 When I run cabal check I get the following message: $ cabal check The following errors will cause portability problems on other environments: * The package is missing a Setup.hs or Setup.lhs script. Hackage would reject this package. ...but except this the package builds fine so far and the executable runs fine. So what does this exactly mean? ovidiu ------------------------------ Message: 3 Date: Thu, 28 Jul 2011 14:47:43 +0200 From: Daniel Fischer <daniel.is.fisc...@googlemail.com> Subject: Re: [Haskell-beginners] cabal check complains about missing Setup.hs To: beginners@haskell.org Message-ID: <201107281447.44048.daniel.is.fisc...@googlemail.com> Content-Type: Text/Plain; charset="iso-8859-1" On Thursday 28 July 2011, 14:17:04, Ovidiu Deac wrote: > When I run cabal check I get the following message: > > $ cabal check > The following errors will cause portability problems on other > environments: * The package is missing a Setup.hs or Setup.lhs script. > > Hackage would reject this package. > > > ...but except this the package builds fine so far and the executable > runs fine. > > So what does this exactly mean? It means that, while cabal can build packages with the `simple' build type without a Setup.[l]hs, other ways to build and install a package, in particular the old $ runhaskell ./Setup.hs configure $ runhaskell ./Setup.hs build $ runhaskell ./Setup.hs install need a Setup.[l]hs. Most of the time the simple module Main (main) where import Distribution.Simple main :: IO () main = defaultMain works. If it doesn't, probably even cabal won't be able to build the package without a Setup script. Cheers, Daniel ------------------------------ Message: 4 Date: Thu, 28 Jul 2011 16:07:14 +0300 From: Ovidiu Deac <ovidiud...@gmail.com> Subject: Re: [Haskell-beginners] cabal check complains about missing Setup.hs To: Daniel Fischer <daniel.is.fisc...@googlemail.com>, beginners <beginners@haskell.org> Message-ID: <CAKVsE7sPPMgeXq73dxMG2WC2=tYEdR-dstPmYbGoXve=fnu...@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Thanks for the explanation. And if I want to add the package in Hackage then I should provide a Setup.hs On Thu, Jul 28, 2011 at 3:47 PM, Daniel Fischer <daniel.is.fisc...@googlemail.com> wrote: > On Thursday 28 July 2011, 14:17:04, Ovidiu Deac wrote: >> When I run cabal check I get the following message: >> >> $ cabal check >> The following errors will cause portability problems on other >> environments: * The package is missing a Setup.hs or Setup.lhs script. >> >> Hackage would reject this package. >> >> >> ...but except this the package builds fine so far and the executable >> runs fine. >> >> So what does this exactly mean? > > It means that, while cabal can build packages with the `simple' build type > without a Setup.[l]hs, other ways to build and install a package, in > particular the old > > $ runhaskell ./Setup.hs configure > $ runhaskell ./Setup.hs build > $ runhaskell ./Setup.hs install > > need a Setup.[l]hs. Most of the time the simple > > module Main (main) where > > import Distribution.Simple > > main :: IO () > main = defaultMain > > works. If it doesn't, probably even cabal won't be able to build the > package without a Setup script. > > Cheers, > Daniel > ------------------------------ Message: 5 Date: Thu, 28 Jul 2011 19:42:22 -0400 From: Jake Penton <d...@arqux.com> Subject: [Haskell-beginners] question on types To: Haskell Beginners <beginners@haskell.org> Message-ID: <b8652fc3-b605-4b22-b36d-8b87fde04...@arqux.com> Content-Type: text/plain; charset="us-ascii" Yikes. I have been doing a fair bit of productive programming in Haskell, thinking that I am making a bit of progress. Then I hit something that is apparently *really simple* that I do not understand at all. How discouraging. Here is the code that makes me realize I don't understand types or type inference very well at all yet: f :: a f = 1 When I try to load the above, ghci gives me: No instance for (Num a) arising from the literal `2' In the expression: 2 In an equation for `f': f = 2 Failed, modules loaded: none. Ok, so then I try: g:: (Num a) => a g = 2 This compiles. Why? I mean, why is the first example (defining f) wrong, but the second example (defining g) ok? A slight variation on this is: h:: a h = 'a' to which ghci replies: Couldn't match type `a' with `Char' `a' is a rigid type variable bound by the type signature for c :: a at /Users/David/Project/EoP/ch04/weak.hs:114:1 In the expression: 'a' In an equation for `c': c = 'a' This last example is probably the most basic one which I need to understand. But, why is the problem apparently a different one than in the definition of "f" above? Of course, I cannot think of a reason to actually define things as shown above under ordinary circumstances. The code above is just boiled down to the simplest case I could find to illustrate my confusion. I guess I interpret "f::a" to mean "f is some (any) type a". So why can't it be whatever "1" is, which I suppose is Integer. What is the type system looking for? And why does the constraint (Num a) make things ok? Please point me in the direction of any reading I should do to clear up my confusion. TIA. - Jake - -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.haskell.org/pipermail/beginners/attachments/20110728/d96c1840/attachment-0001.htm> ------------------------------ Message: 6 Date: Thu, 28 Jul 2011 20:23:11 -0400 From: Brandon Allbery <allber...@gmail.com> Subject: Re: [Haskell-beginners] question on types To: Jake Penton <d...@arqux.com> Cc: Haskell Beginners <beginners@haskell.org> Message-ID: <cakfcl4voo_xpj9hzmr5ifiaogd-yqixfy3muortwsrmteph...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" On Thu, Jul 28, 2011 at 19:42, Jake Penton <d...@arqux.com> wrote: > h:: a > h = 'a' > > to which ghci replies: > > Couldn't match type `a' with `Char' > `a' is a rigid type variable bound by > the type signature for c :: a > at /Users/David/Project/EoP/ch04/weak.hs:114:1 > In the expression: 'a' > In an equation for `c': c = 'a' > > This last example is probably the most basic one which I need to > understand. But, why is the problem apparently a different one than in the > definition of "f" above? > The other one was complicated by polymorphism: a numeric literal is compiled into a call to fromIntegral, whose result type is Num a => a. The problem is that, when you say something's type is "a", you are not saying "pick an appropriate type for me"; you are saying "whoever invokes this can ask for any type it wants" (equivalently: "I promise to be able to produce *any possible* type"). But then you give the value as Num a => a in the first example and Char in the second example, neither of which is "any possible type". An explicit type is a complete contract; having contracted to produce an "a" (any type), you can't then offer only a Char or a Num a => a. You have to satisfy the contract which says "any type", otherwise you're doing the type checking equivalent of a bait-and-switch. You can't express "pick a type for me" in a type signature; types are concrete, and a type variable in a signature is a concrete "anything", meaning the caller can request whatever it wants and you must produce it. The type must be *completely* described by the signature; what it says is what you're committed to, and you can't then offer something else. If you need a partial type signature, there are some tricks you can use which let you force types in the implementation without specifying a concrete signature (see http://okmij.org/ftp/Haskell/types.html#partial-sigs). -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.haskell.org/pipermail/beginners/attachments/20110728/e6a22770/attachment-0001.htm> ------------------------------ Message: 7 Date: Fri, 29 Jul 2011 01:23:51 +0100 From: Julian Porter <julian.por...@porternet.org> Subject: Re: [Haskell-beginners] question on types To: Jake Penton <d...@arqux.com> Cc: Haskell Beginners <beginners@haskell.org> Message-ID: <0d3e3169-259b-47eb-8ff6-76a09748a...@porternet.org> Content-Type: text/plain; charset="us-ascii" The point is that in f::a you are saying that f is of an undefined type a. But in f=1 you're saying that a must be a type that supports the value 1, and not all do (eg strings, booleans). Therefore you have to tell the compiler that you are constraining a to allow it to take the value 1, hence the constraint Num a, which does just that. The error message is telling you just this: it can't find a constraint that tells it that a is in the class Num, so it is complaining because what you have written could fail if you used f in a context where it was inferred to have a non numerical type. Constraints allow the type-inference engine to spot such errors, saving you from terrible grief in debugging. Sent from my iPhone On 29 Jul 2011, at 00:42, Jake Penton <d...@arqux.com> wrote: > Yikes. > > I have been doing a fair bit of productive programming in Haskell, thinking > that I am making a bit of progress. Then I hit something that is apparently > *really simple* that I do not understand at all. How discouraging. > > Here is the code that makes me realize I don't understand types or type > inference very well at all yet: > > f :: a > f = 1 > > When I try to load the above, ghci gives me: > > No instance for (Num a) > arising from the literal `2' > In the expression: 2 > In an equation for `f': f = 2 > Failed, modules loaded: none. > > > Ok, so then I try: > > g:: (Num a) => a > g = 2 > > This compiles. > > Why? I mean, why is the first example (defining f) wrong, but the second > example (defining g) ok? > > A slight variation on this is: > > h:: a > h = 'a' > > to which ghci replies: > > Couldn't match type `a' with `Char' > `a' is a rigid type variable bound by > the type signature for c :: a > at /Users/David/Project/EoP/ch04/weak.hs:114:1 > In the expression: 'a' > In an equation for `c': c = 'a' > > This last example is probably the most basic one which I need to understand. > But, why is the problem apparently a different one than in the definition of > "f" above? > > Of course, I cannot think of a reason to actually define things as shown > above under ordinary circumstances. The code above is just boiled down to the > simplest case I could find to illustrate my confusion. > > I guess I interpret "f::a" to mean "f is some (any) type a". So why can't it > be whatever "1" is, which I suppose is Integer. What is the type system > looking for? And why does the constraint (Num a) make things ok? > > Please point me in the direction of any reading I should do to clear up my > confusion. > > TIA. > > - Jake - > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://www.haskell.org/mailman/listinfo/beginners -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.haskell.org/pipermail/beginners/attachments/20110729/30fc4ec0/attachment.htm> ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 37, Issue 63 *****************************************