Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
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 <[email protected]>
Subject: Re: [Haskell-beginners] question on types
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
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 <[email protected]> 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 <[email protected]>
Subject: Re: [Haskell-beginners] question on types
To: [email protected]
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] question on types
To: Jake Penton <[email protected]>
Cc: Haskell Beginners <[email protected]>
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 <[email protected]> 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 [email protected]
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 <[email protected]>
Subject: Re: [Haskell-beginners] question on types
To: Brandon Allbery <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
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 <[email protected]>
Subject: Re: [Haskell-beginners] lazyness and tail recursion
To: Will Ness <[email protected]>, beginners <[email protected]>
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 <[email protected]> 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 <[email protected]>* wrote:
>
>
> From: Ovidiu Deac <[email protected]>
> Subject: Re: [Haskell-beginners] lazyness and tail recursion
> To: "Will Ness" <[email protected]>
> Cc: [email protected]
> 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
> <[email protected]<http://us.mc1145.mail.yahoo.com/mc/[email protected]>>
> 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
> > [email protected]<http://us.mc1145.mail.yahoo.com/mc/[email protected]>
> > 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
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 37, Issue 64
*****************************************
