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: question on types (Jake Penton) 2. Re: question on types (Daniel Fischer) 3. Re: question on types (Brandon Allbery) 4. Re: question on types (Jake Penton) 5. Re: lazyness and tail recursion (Ovidiu Deac) ---------------------------------------------------------------------- Message: 1 Date: Thu, 28 Jul 2011 21:26:33 -0400 From: Jake Penton <d...@arqux.com> Subject: Re: [Haskell-beginners] question on types To: Haskell Beginners <beginners@haskell.org> Message-ID: <2a2931c7-a6d1-4ac5-94d0-dc5b83940...@arqux.com> Content-Type: text/plain; charset="us-ascii" On 2011-07-28, at 8:23 PM, Brandon Allbery wrote: > 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). > Ok, thanks. I have some studying to do about haskell types, clearly. Does that mean then that there is no definition possible of f other than 'undefined'? I mean this compiles: f::a f = undefined But is there any other possible second line defining f? - Jake - -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.haskell.org/pipermail/beginners/attachments/20110728/b247543b/attachment-0001.htm> ------------------------------ Message: 2 Date: Fri, 29 Jul 2011 04:19:39 +0200 From: Daniel Fischer <daniel.is.fisc...@googlemail.com> Subject: Re: [Haskell-beginners] question on types To: beginners@haskell.org Message-ID: <201107290419.39446.daniel.is.fisc...@googlemail.com> Content-Type: Text/Plain; charset="utf-8" On Friday 29 July 2011, 03:26:33, Jake Penton wrote: > > Ok, thanks. I have some studying to do about haskell types, clearly. > > Does that mean then that there is no definition possible of f other than > 'undefined'? I mean this compiles: > > f::a > f = undefined > > But is there any other possible second line defining f? Sure, you can write the same thing in many different ways: f :: a f = f f :: a f = let x = x in x f :: a f = error "Foo" but all definitions of "f :: a" that compile yield (some kind of) bottom, since _|_ is the only value that is common to all types (whether an attempt to evaluate such a value yields actual nontermination or an exception message depends; the first two don't terminate in ghci but result in "<<loop>>" when used in a compiled programme). > > - Jake - ------------------------------ Message: 3 Date: Thu, 28 Jul 2011 22:22:09 -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: <cakfcl4xgm0rdndz9sfacqdez9c-lq0zh-0tykjldbvjg7sy...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" On Thu, Jul 28, 2011 at 21:26, Jake Penton <d...@arqux.com> wrote: > Does that mean then that there is no definition possible of f other than > 'undefined'? I mean this compiles: > > f::a > f = undefined > > But is there any other possible second line defining f? > Only more complicated forms of the same thing: > f = error "impossible value" > f = let x = x in x -- infinite evaluation You'll occasionally see discussion of the role of "bottom" in the language; that's what this is. Technically, bottom is the least defined value of a type, and since in standard Haskell all types are "lifted" (their values are computed via thunks of some kind; this is what enables laziness) bottom inhabits every type, and is the only "value" that does so. (Various extensions introduce and make use of unlifted types, which are always strict; as such, they can never really be bottom, as any attempt to use bottom in the context of an unlifted type leads to a runtime error, infinite loop, crash, or other form of nontermination.) -- 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/7c510039/attachment-0001.htm> ------------------------------ Message: 4 Date: Thu, 28 Jul 2011 23:47:13 -0400 From: Jake Penton <d...@arqux.com> Subject: Re: [Haskell-beginners] question on types To: Brandon Allbery <allber...@gmail.com> Cc: Haskell Beginners <beginners@haskell.org> Message-ID: <6fa50524-1741-4373-be89-779a553c6...@arqux.com> Content-Type: text/plain; charset=us-ascii Well, thanks everyone. I'm getting there slowly. I have had less success learning Haskell by just using it than any other language I have tackled. I seem to need to cycle regularly between some theoretical study and practical use. Actually, starting in September I shall be taking a grad course on languages. The text is Types and Programming Languages by Pierce. I looked quickly at the book after posting my question, and believe that the course will plug some major gaps in my understanding of types. - Jake - ------------------------------ Message: 5 Date: Fri, 29 Jul 2011 10:48:25 +0300 From: Ovidiu Deac <ovidiud...@gmail.com> Subject: Re: [Haskell-beginners] lazyness and tail recursion To: Will Ness <will_...@yahoo.com>, beginners <beginners@haskell.org> Message-ID: <CAKVsE7st=NfK_XwBBm4C74mpf66=goja-koift1nxl913rj...@mail.gmail.com> Content-Type: text/plain; charset="iso-8859-1" Now I think I understand. Thanks for the explanation! ovidiu On Fri, Jul 29, 2011 at 12:04 AM, Will Ness <will_...@yahoo.com> wrote: > ... the start of the function, so to speak. > > If we have (f x = a : f b), the distance between this entry into f, and the > next one, has constant length: (a :). If we have (f x = "123" ++ f y), it's > constant too, just bigger than 1 - no problem, it will all get consumed in > constant number of steps, there's no explosion in number of operations. > > But if we have (f x = f a ++ f b) e.g., then (f a) will add some, and its > calls will get some, and it all grows out of control - and all this needs to > be maintained by the system, to get to the final (f b). Not nice. > > But anyway I'm no expert; it's just how I explain it to myself, from > Prolog's "tail recursion modulo cons" perspective. We don't need to wait for > a function to return to prepend something onto its result; we prepent this > to a yet-to-be-filled list, and pass that stump into the tail-recursive > function. Presto, all it fine. Same in Haskell, no second function call will > get actually called until what's before it gets consumed - so there's no > proble if that's constant in size. But I repeat myself. :) > > Cheers, > Will > > > --- On *Thu, 7/28/11, Ovidiu Deac <ovidiud...@gmail.com>* wrote: > > > From: Ovidiu Deac <ovidiud...@gmail.com> > Subject: Re: [Haskell-beginners] lazyness and tail recursion > To: "Will Ness" <will_...@yahoo.com> > Cc: beginners@haskell.org > Date: Thursday, July 28, 2011, 10:27 AM > > > 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<http://us.mc1145.mail.yahoo.com/mc/compose?to=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://us.mc1145.mail.yahoo.com/mc/compose?to=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/1ed3dc72/attachment.htm> ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 37, Issue 64 *****************************************