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: Re: question about styles of recursion (Brent Yorgey)
2. Re: beginner's type error (Michael Mossey)
3. Re: beginner's type error (Brent Yorgey)
4. Re: beginner's type error (Thomas Davie)
5. Re: beginner's type error (Brent Yorgey)
6. Re: beginner's type error (Brent Yorgey)
7. pattern matching to data inside a list (Michael Mossey)
8. Re: Re: Tutorial/Book with Exercises (Zachary Turner)
----------------------------------------------------------------------
Message: 1
Date: Fri, 27 Mar 2009 08:55:59 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Re: question about styles of
recursion
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Thu, Mar 26, 2009 at 03:23:01PM -0700, Michael Mossey wrote:
>
> But back to the gist of my question last night: I am aware that most
> examples of recursion presented in the books so far do their processing "as
> the recursion unwinds." In other words:
>
> length :: [a] -> Int
> length [] = 0
> length (x:xs) = 1 + length xs
>
> This function goes deeper and deeper into the recursion before doing any
> calculation, then does all the sums "on the way back out."
Right, this is equivalent to
length = foldr (+) 0
and results in expressions like (1 + (1 + (1 + (1 + ...)))), which
isn't good in this particular case, since none of the additions can be
performed until the very end of the list is reached, and all the sums
are indeed done "on the way back out". There are some cases, however
(such as when the result is some data structure that can be computed
lazily, like another list) when this is exactly what you want.
> Being an imperative programmer, I keep trying to write loops that
> accumulate "on the way down", like this:
>
> length' :: Int -> [a] -> Int
> length' s [] = s
> length' s (x:xs) = length' (s+1) xs
>
> length :: [a] -> Int
> length xs = length' 0 xs
And this is equivalent to
length = foldl (+) 0
and results in expressions like (((((0 + 1) + 1) + 1) + 1) + ... ).
This looks better at first glance, since the sums can start
accumulating as you go. However, since Haskell is lazy, this
particular version is no better, because the sums won't be evaluated
until the result is needed anyway: instead of accumulating a number,
you end up accumulating a giant thunk (unevaluated expression) which
is only evaluated when its result is finally needed, after the call to
length has already finished! So as long as you don't call length on
really long lists, you might as well use your first version---if
you're going to blow the stack on long lists anyway, you might as well
do it in a more natural style. =) But read on...
What we'd like is some way to force the accumulator to be evaluated as
we recurse down the list---and this is exactly what the foldl'
function (from Data.List) does, by introducing a bit of strictness.
So the best way to write length is actually
length = foldl' (+) 0.
Whenever you see this 'accumulator' pattern over lists---some
recursive function which recurses over a list while accumulating some
small summary value---think foldl'.
> I suppose both forms are valid, but the first form seems to be most natural
> in most situations I've encountered in the exercises.
The first is indeed more natural. Generally speaking, if you find
yourself using accumulating parameters, there's probably a simpler way
to do it, or some library function that already does exactly what you
want to do. But it takes experience to learn and recognize such
situations.
-Brent
------------------------------
Message: 2
Date: Fri, 27 Mar 2009 06:01:15 -0700
From: Michael Mossey <[email protected]>
Subject: Re: [Haskell-beginners] beginner's type error
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Peter Verswyvelen wrote:
>
> You can also get rid of the parentheses like this:
>
> thing n = n + fromIntegral $ round $ sqrt n
I'm having a hard time finding an explanation of the dollar signs. What
do they do? It looks like they break up the left-ro-right association of
function names to arguments.
As a beginner, I love how Haskell is filled with so many good ideas, in
many areas. The basic concept of functional programming is good, but
also Haskell has beautiful syntax that's just pleasing to look at, and
also has many convenient features which may not quite qualify as
"beautiful" or "elegant" but are just convenient (still a worthy thing).
Languages that borrow from Haskell, like Python's list comprehensions,
invariably are much dumbed-down implementations. In Python, list
comprehensions don't have guards or pattern matching. (Technically you
can put in a guard via an if statement, but you are doing a lot more
typing at that point.)
Thanks,
Mike
------------------------------
Message: 3
Date: Fri, 27 Mar 2009 09:07:10 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] beginner's type error
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Thu, Mar 26, 2009 at 10:01:07PM +0000, Ivan Moore wrote:
> Hi all,
>
> consider this very small function:
>
> thing n = n + round(sqrt n)
Here's what's going on: since you call sqrt on n, it must have some
type which is an instance of Floating. However, round can return any
type which is an instance of Integral, and since you are adding n to
it, n must have the same type.
This is the takeaway point here: sqrt requires some floating-point
type (like Float or Double), but round returns an Integral type (like
Int or Integer) and n can't be both. In particular you can't call
sqrt on an Integral value. So the fix is to use fromIntegral to
convert:
thing n = n + round (sqrt (fromIntegral n))
>
> It loads into ghci with no warnings.
The reason (which is a bit confusing) is that it typechecks just
fine---if there *were* a type which is an instance of both Integral
and Floating (and I guess round needs RealFrac as well), n could have
that type. There isn't such a type in the standard libraries, but in
theory you could make up your own type which is an instance of both.
> When I try to run "thing 10" I get:
>
> *Main> :load c:\temp\statictype.hs
> [1 of 1] Compiling Main ( C:\temp\statictype.hs, interpreted )
> Ok, modules loaded: Main.
> *Main> thing 10
>
> <interactive>:1:0:
> Ambiguous type variable `t' in the constraints:
> `Integral t' arising from a use of `thing' at <interactive>:1:0-7
> `RealFrac t' arising from a use of `thing' at <interactive>:1:0-7
> `Floating t' arising from a use of `thing' at <interactive>:1:0-7
> Probable fix: add a type signature that fixes these type variable(s)
>
> I have tried to add various type signatures (without really knowing
> what I'm doing!) and haven't been able to get it to work.
>
> I am confused about a few things related to this:
> (a) what type signature fixes it and why it needs any help - it looks
> like the sort of thing that type inference shouldn't need any help
> with
The error message is particularly unhelpful here. Adding a type
signature would only help if you actually had some type which was both
Integral and Floating, but you don't.
> (b) it looks like a runtime type error and I thought you didn't get
> runtime type errors in Haskell
You don't. This isn't a runtime type error; the error was generated
while trying to typecheck the expression 'thing 10' before evaluating
it.
> (c) if I substitute 10 for n and do "10 + round(sqrt 10)" I get the
> expected answer 13
This is because numeric literals (like 10) are polymorphic---they can
have any numeric type. In this case, type inference correctly figures
out that the first 10 should have type Integer, and the second 10
should have type Double. The difference is that they are not
constrained to have the same type---unlike the two occurrences of 'n'
in your original function.
Confusing, isn't it! It's a shame that numeric types can be so
confusing, since that's usually one of the first things that people
run into when learning the language. But I hope this is helpful.
Feel free to ask if you have more questions.
-Brent
------------------------------
Message: 4
Date: Fri, 27 Mar 2009 14:11:03 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] beginner's type error
To: Michael Mossey <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 27 Mar 2009, at 14:01, Michael Mossey wrote:
>
>
> Peter Verswyvelen wrote:
>> You can also get rid of the parentheses like this:
>> thing n = n + fromIntegral $ round $ sqrt n
>
> I'm having a hard time finding an explanation of the dollar signs.
> What do they do? It looks like they break up the left-ro-right
> association of function names to arguments.
You're pretty much there!
The $ function is simply "apply":
f $ a = f a
The difference is that this version of application (as opposed to the
version written as ' ') has very very low precidence, and can be used
to essentially mean "apply this to the whole expression on my right".
Of note though, using chains of ($)s as peter did is commonly
considered bad style, instead, one should use (.) to build up a
function, and then apply it, so not:
fromIntegral $ round $ sqrt n
But instead:
fromIntegral . round . sqrt $ n
Why? Because the latter one has more valid expressions and is
therefor easier to refactor. For example, in the latter one I may
deside that (round . sqrt) is a useful function in itself (lets call
it integralSqrt) and refactor:
fromIntegral . integralSqrt $ n
integralSqrt = round . sqrt
With this style, this is simply a matter of copy/paste.
> As a beginner, I love how Haskell is filled with so many good ideas,
> in many areas. The basic concept of functional programming is good,
> but also Haskell has beautiful syntax that's just pleasing to look
> at, and also has many convenient features which may not quite
> qualify as "beautiful" or "elegant" but are just convenient (still a
> worthy thing).
I'm not sure, most of the convenient things I use in Haskell are also
beautiful and elegant, did you have something in mind?
Thanks
Bob
------------------------------
Message: 5
Date: Fri, 27 Mar 2009 09:11:14 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] beginner's type error
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Fri, Mar 27, 2009 at 06:01:15AM -0700, Michael Mossey wrote:
>
>
> Peter Verswyvelen wrote:
>> You can also get rid of the parentheses like this:
>> thing n = n + fromIntegral $ round $ sqrt n
>
> I'm having a hard time finding an explanation of the dollar signs. What do
> they do? It looks like they break up the left-ro-right association of
> function names to arguments.
($) is just function application. It is defined as:
f $ x = f x
This looks useless, of course, but it also has very low precedence, so
it is often used to avoid parentheses. For example,
(foo bar) (baz t)
can't be written without the parentheses, since that would be parsed
as ((foo bar) baz) t, but it can be written as
foo bar $ baz t
> As a beginner, I love how Haskell is filled with so many good ideas, in
> many areas. The basic concept of functional programming is good, but also
> Haskell has beautiful syntax that's just pleasing to look at, and also has
> many convenient features which may not quite qualify as "beautiful" or
> "elegant" but are just convenient (still a worthy thing).
As a non-beginner, I love this too. So I think you're on to something. =)
-Brent
------------------------------
Message: 6
Date: Fri, 27 Mar 2009 09:17:39 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] beginner's type error
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>
> thing n = n + fromIntegral (round (sqrt n))
>
> thing n = n + round (sqrt (fromIntegral n))
Pop quiz for beginners: both of these solve the original problem, but
they are not quite the same. What is the difference? (Do not answer
this question if you are not a beginner!)
-Brent
------------------------------
Message: 7
Date: Fri, 27 Mar 2009 06:25:43 -0700
From: Michael Mossey <[email protected]>
Subject: [Haskell-beginners] pattern matching to data inside a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Is there a way to pattern match to a list argument and get a list? For
example, I have this:
-- A LayoutItem has a center position (point), and the four ints are
-- "left width", "rigth width", "top height", and "bottom height"
data LayoutItem = LayoutItem Point Int Int Int Int
deriving Show
-- This computes the left width of a group of composited LayoutItem.
compositeLeftWidth :: [LayoutItem] -> Int
compositeLeftWidth items = let
itemsPosX = [ x | LayoutItem (Point (x,_)) _ _ _ _ <- items ]
itemsLW = [ lw | LayoutItem _ lw _ _ _ <- items ]
z = zipWith (\x y -> x-y+1) itemsPosX itemsLW
in (minimum z) - 1
What I'm wondering is if I could somehow do something like
compositeLeftWidth [ LayoutItem Point( x, _ ) lw _ _ _ ] = ...
and that x and lw would each be the lists I'm calling itemsPosX and
itemsLW above.
Thanks,
Mike
PS Let me repeat my request to find out how to install SOE "on the
library path." I know I'm impatient about this, but it seems simple
enough, and it's driving me crazy that I can only write software in the
same directory where I've installed SOE.
------------------------------
Message: 8
Date: Fri, 27 Mar 2009 08:27:50 -0500
From: Zachary Turner <[email protected]>
Subject: Re: [Haskell-beginners] Re: Tutorial/Book with Exercises
To: Michael Mossey <[email protected]>
Cc: [email protected], Jason White <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
I haven't actually gotten to this exercise yet, but I feel like this is
probably related: http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html.
I'm not sure if it will give you some pointers in the right direction. It
basically explains how to "abstract out" the recursive part of a function
into a separate function, which is basically what you need.
On Fri, Mar 27, 2009 at 7:21 AM, Michael Mossey <[email protected]>wrote:
>
>
> Jason White wrote:
>
>> Michael Mossey <[email protected]> wrote:
>>
>> YAHT has some hard exercises, early on. He introduces continuations in
>>> chapter 4, briefly, and then casually asks you to rewrite map and filter in
>>> continuation-passing-style. I was stumped.
>>>
>>
>> So am I.
>>
>> Do you have any hints for these, without giving the answers away (I know
>> the
>> answers are in the appendix if I really need them)?
>>
>> Well, I've got some bad news for you. He doesn't include the answers to
> the CPS-related questions. Note: YAHT seems to be incomplete in a number of
> ways, because there are chapter headings that exist only as stubs. However,
> it's a terrific resource, and my thanks to Hal.
>
> I decided to just move on, and I'll come back to continuations when I find
> them in another book.
>
> Mike
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090327/824af438/attachment.htm
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 35
****************************************
