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:  IO loops with tail call (edgar klerks)
   2. Re:  IO loops with tail call (Daniel Fischer)
   3.  case as guards in lambda functions (Russ Abbott)
   4. Re:  case as guards in lambda functions (Daniel Fischer)
   5. Re:  IO loops with tail call (edgar klerks)
   6. Re:  case as guards in lambda functions (Brent Yorgey)


----------------------------------------------------------------------

Message: 1
Date: Wed, 10 Nov 2010 18:25:37 +0100
From: edgar klerks <[email protected]>
Subject: Re: [Haskell-beginners] IO loops with tail call
To: Yasuyuki Ogawa <[email protected]>
Cc: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"

Hi Yasuyuki,

I must admit, It is not clear to me. But I think a reference to the head of
the list is somehow used as an argument to the recursive function, which
adds the next value to the list. So that it is tail-recursive again. Or
something like that.

But I may also be completely off.

Greets,

Edgar


On Tue, Nov 9, 2010 at 1:17 PM, Yasuyuki Ogawa <[email protected]>wrote:

> Hi Edgar,
>
> Thank you for interesting wiki pages!
> Roughly speaking, because of laziness, tail recursion is not always
> necessary, modulo cons but useful enough...or something like that?
> I'll study!
>
> -- Yasuyuki
>
>
> (2010/11/08 19:21), edgar klerks wrote:
>
>> Hi Yasuyuki,
>>
>> Here is some resource Brent produced, why tail-recursion isn't that
>> important in haskell:
>>
>> http://www.haskell.org/pipermail/haskell-cafe/2009-March/058607.html
>> (http://www.haskell.org/haskellwiki/Tail_recursion)
>>
>> I think it is nice to have some background (and it is pretty interesting).
>>
>> Greets,
>>
>> Edgar
>>
>
>
> --------------------------------------
> Get the new Internet Explorer 8 optimized for Yahoo! JAPAN
> http://pr.mail.yahoo.co.jp/ie8/
> _______________________________________________
> 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/20101110/b3f7fb82/attachment-0001.html

------------------------------

Message: 2
Date: Wed, 10 Nov 2010 19:53:18 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] IO loops with tail call
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain;  charset="utf-8"

On Wednesday 10 November 2010 18:25:37, edgar klerks wrote:
> Hi Yasuyuki,
>
> I must admit, It is not clear to me. But I think a reference to the head
> of the list is somehow used as an argument to the recursive function,
> which adds the next value to the list. So that it is tail-recursive
> again. Or something like that.

One point is that a tail-recursive function can't deliver anything until it 
has reached the end of the recursion, but laziness allows to deliver 
partial results before that (not always, however; sum :: [Int] -> Int needs 
to traverse the entire list, so there's a point where tail-recursion [with 
a strict accumulator] is the way to go).

Consider

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

Not being tail-recursive, it can deliver its result (almost) immediately.
The result is a constructor, (:), applied to two thunks. If the caller 
consumes the result appropriately, the computation can run in constant 
space.
The important thing is that the recursive call is in a lazy argument 
position of the overall result, so the recursion may end prematurely if the 
caller doesn't need the full result.

If you define map with a tail-recursive worker, the entire result list has 
to be constructed before the caller can inspect any of it, so it would 
require at least O(length list) space - particularly wasteful if the caller 
is "take k" for sufficiently small k and doesn't work at all on infinite 
lists.

Tail-recursion has its uses in Haskell, but since Haskell's evaluation 
model is different from e.g. Lisp's, it's not so important. As a catch-
phrase: "(non-tail-)recursion doesn't eat stack frames in Haskell".

>
> But I may also be completely off.
>
> Greets,
>
> Edgar


------------------------------

Message: 3
Date: Wed, 10 Nov 2010 12:13:26 -0800
From: Russ Abbott <[email protected]>
Subject: [Haskell-beginners] case as guards in lambda functions
To: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"

I have often wanted to use a guard in a lambda function and had thought it
wasn't possible. But apparently the case construct allows a viable approach.
Here is a silly example.

testCase = map
             (\xs -> case xs of
                     []              -> "empty list"
                     [y] | y < 5     -> "small singleton"
                         | otherwise -> "large singleton"
                     _               -> "multi-element list")


> testCase [[], [2], [7], [1,2,3]]
["empty","small singleton","large singleton","multi-element list"]

It seems particularly useful to be able to include both patterns and guards
in case expressions. I haven't seen this usage anywhere. Is it considered
bad form?
*
-- Russ *
-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
http://www.haskell.org/pipermail/beginners/attachments/20101110/575b94b3/attachment-0001.html

------------------------------

Message: 4
Date: Wed, 10 Nov 2010 21:58:15 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] case as guards in lambda functions
To: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain;  charset="utf-8"

On Wednesday 10 November 2010 21:13:26, Russ Abbott wrote:
> I have often wanted to use a guard in a lambda function and had thought
> it wasn't possible. But apparently the case construct allows a viable
> approach. Here is a silly example.
>
> testCase = map
>              (\xs -> case xs of
>                      []              -> "empty list"
>                      [y] | y < 5     -> "small singleton"
>
>                          | otherwise -> "large singleton"
>
>                      _               -> "multi-element list")
>
> > testCase [[], [2], [7], [1,2,3]]
>
> ["empty","small singleton","large singleton","multi-element list"]
>
> It seems particularly useful to be able to include both patterns and
> guards in case expressions. I haven't seen this usage anywhere.

If it's not a very small case-expression, usually one puts it in a where 
clause,

map f list
  where
    f xs = case xs of
             ...

since a huge lambda expression tends to obscure the overall structure of 
the expression.


> Is it considered bad form?

If the expression becomes too large.

> *
> -- Russ *



------------------------------

Message: 5
Date: Wed, 10 Nov 2010 22:47:07 +0100
From: edgar klerks <[email protected]>
Subject: Re: [Haskell-beginners] IO loops with tail call
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"

Thanks for your clear explanation. I understand the role of laziness now.

On Wed, Nov 10, 2010 at 7:53 PM, Daniel Fischer <[email protected]>wrote:

> On Wednesday 10 November 2010 18:25:37, edgar klerks wrote:
> > Hi Yasuyuki,
> >
> > I must admit, It is not clear to me. But I think a reference to the head
> > of the list is somehow used as an argument to the recursive function,
> > which adds the next value to the list. So that it is tail-recursive
> > again. Or something like that.
>
> One point is that a tail-recursive function can't deliver anything until it
> has reached the end of the recursion, but laziness allows to deliver
> partial results before that (not always, however; sum :: [Int] -> Int needs
> to traverse the entire list, so there's a point where tail-recursion [with
> a strict accumulator] is the way to go).
>
> Consider
>
> map :: (a -> b) -> [a] -> [b]
> map f [] = []
> map f (x:xs) = f x : map f xs
>
> Not being tail-recursive, it can deliver its result (almost) immediately.
> The result is a constructor, (:), applied to two thunks. If the caller
> consumes the result appropriately, the computation can run in constant
> space.
> The important thing is that the recursive call is in a lazy argument
> position of the overall result, so the recursion may end prematurely if the
> caller doesn't need the full result.
>
> If you define map with a tail-recursive worker, the entire result list has
> to be constructed before the caller can inspect any of it, so it would
> require at least O(length list) space - particularly wasteful if the caller
> is "take k" for sufficiently small k and doesn't work at all on infinite
> lists.
>
> Tail-recursion has its uses in Haskell, but since Haskell's evaluation
> model is different from e.g. Lisp's, it's not so important. As a catch-
> phrase: "(non-tail-)recursion doesn't eat stack frames in Haskell".
>
> >
> > But I may also be completely off.
> >
> > Greets,
> >
> > Edgar
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
http://www.haskell.org/pipermail/beginners/attachments/20101110/b123dc5c/attachment-0001.html

------------------------------

Message: 6
Date: Wed, 10 Nov 2010 18:15:31 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] case as guards in lambda functions
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii

On Wed, Nov 10, 2010 at 09:58:15PM +0100, Daniel Fischer wrote:
> On Wednesday 10 November 2010 21:13:26, Russ Abbott wrote:
> > I have often wanted to use a guard in a lambda function and had thought
> > it wasn't possible. But apparently the case construct allows a viable
> > approach. Here is a silly example.
> >
> > testCase = map
> >              (\xs -> case xs of
> >                      []              -> "empty list"
> >                      [y] | y < 5     -> "small singleton"
> >
> >                          | otherwise -> "large singleton"
> >
> >                      _               -> "multi-element list")
> >
> > > testCase [[], [2], [7], [1,2,3]]
> >
> > ["empty","small singleton","large singleton","multi-element list"]
> >
> > It seems particularly useful to be able to include both patterns and
> > guards in case expressions. I haven't seen this usage anywhere.
> 
> If it's not a very small case-expression, usually one puts it in a where 
> clause,
> 
> map f list
>   where
>     f xs = case xs of
>              ...

Yes, and doing it this way obviates the need for a case expression:

  map f list
    where 
      f [] = ...
      f [y] | y < 5 = ...
 
> > Is it considered bad form?
> 

Using patterns and guards in case expressions isn't necessarily bad
form.  But it doesn't seem to be that common.

-Brent


------------------------------

_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners


End of Beginners Digest, Vol 29, Issue 14
*****************************************

Reply via email to