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 (Brent Yorgey)
2. General primitive recursion (Russ Abbott)
3. Re: editing a list (Bastian Erdn??)
4. Re: IO loops with tail call (Yasuyuki Ogawa)
5. Re: editing a list (Stephen Tetley)
----------------------------------------------------------------------
Message: 1
Date: Sat, 6 Nov 2010 15:26:49 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] IO loops with tail call
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sun, Nov 07, 2010 at 01:54:26AM +0900, Yasuyuki Ogawa wrote:
> Hello!
>
> I wrote a simple echo program which end up with input "q":
>
> echo = do
> str <- getLine
> if (str == "q")
> then return ()
> else putStrLn str >> echo
This is a tail call. Yes, if expressions return a value, but here
nothing more is done with that value so the memory used by the current
call to echo can be garbage collected once the recursive call is made.
However, the real answer is: don't worry about it! Because of
Haskell's lazy evaluation, the notion of "tail call" is not very
important. And even if it were, you still shouldn't worry about it:
just write your Haskell programs in the most natural, beautiful style
you can think of. Maybe at some point down the road you will have
to start worrying about optimization. But you should put it off as
long as possible.
-Brent
------------------------------
Message: 2
Date: Sat, 6 Nov 2010 19:14:15 -0700
From: Russ Abbott <[email protected]>
Subject: [Haskell-beginners] General primitive recursion
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Thanks Stephen,
That looks like a nice set of slides.
You're right that what I call the mapFn and the reduceFn could be combined
into one function. Logically, though, I think it's more intuitive if they
are separated. In addition, it seems important to allow for the possibility
of having a function at the terminal point. For example, here's how I would
define merge.
merge xs ys =
recursionEngine
(\(xs, ys) -> null xs || null ys)
(\(xs, ys) -> xs ++ ys)
(:)
(\(x:xs, y:ys) -> min x y)
(\(x:xs, y:ys) -> if x <= y then (xs, y:ys) else (x:xs, ys))
(xs, ys)
I'm not sure how to translate that into the genPR formulation.
merge xs ys =
genPR
(\(xs, ys) -> null xs || null ys)
(\(x:xs, y:ys) -> if x <= y then (xs, y:ys) else (x:xs, ys))
<There is no constant that goes here.>
(\(x:xs, y:ys) merged -> (min x y) : merged)
Besides the problem with the third argument, the fourth argument is awkward
since it must take both heads, take their min, and then add them to the
result of the recursive call. I'd prefer to take the heads and the min in a
separate step as in the fourth argument to recursionEngine.
*-- Russ *
On Sat, Nov 6, 2010 at 2:10 AM, Stephen Tetley wrote:
>
>
> Hello Russ
>
> Richard Kieburtz has a slightly smaller formulation of primitive
> recursion on page 13 of these slides - the fold-like argument 'h'
> doesn't appear to need a change of type:
>
> http://programatica.cs.pdx.edu/P/Programatica%20Logic1.pdf
>
> genPR :: (a -> Bool) -> (a -> a) -> c -> (a -> c -> c) -> a -> c
> genPR p b g h x = if p x then g else h x (genPR p b g h (b x))
>
>
> -- factorial function:
> fact :: Integer -> Integer
> fact = genPR (==0) (subtract 1) 1 (*)
>
> Ignoring changes in argument order, the type of your recursionEngine
> is one term and one type variable larger:
>
> recursionEngine :: (a -> Bool) -> (a -> c) -> (b -> c -> c) -> (a ->
> b) -> (a -> a)-> a -> c
>
> Best wishes
>
> Stephen
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20101106/b793fb8d/attachment-0001.html
------------------------------
Message: 3
Date: Sun, 7 Nov 2010 05:40:33 +0100
From: Bastian Erdn?? <[email protected]>
Subject: Re: [Haskell-beginners] editing a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Nov 2, 2010, at 21:10, Daniel Fischer wrote:
> On Saturday 30 October 2010 16:59:00, Jonathan Phillips wrote:
>> I have a list (more precisely a string) which I'm trying to recurse
>> through, editing sections as I come to it. It's obvious how to do it
>> with a for loop, but I'm doing it all wrong in haskell, as this simple
>> task is running mind-numbingly slowly.
Maybe you should split the string into lines using 'lines' from Data.List, then
divide each line into 23-4-rest chars somehow using 'splitAt', apply the "show
((read str :: Integer) + 1)" part, justify the answer, probably by appending
four spaces and then taking the first four characters, put the 23-changed4-rest
parts back together with ++, and finally join all the lines again with
'unlines'.
> l | l < 4 -> s ++ " " ++ addOneNum' xs (n+4)
> -- guessing it's the same number of spaces for those
I suppose it shall justify the number to length 4. I.e.
>> changeNo v (w:x:y:z:xs) n = case
>> length(s@(show((read([w,x,y,z])::Integer) + 1))) of
>> 0 -> addOneNum (v ++ " ") xs (n+4)
>> 1 -> addOneNum (v ++ s ++ " ") xs (n+4)
>> 2 -> addOneNum (v ++ s ++ " ") xs (n+4)
>> 3 -> addOneNum (v ++ s ++ " ") xs (n+4)
>> 4 -> addOneNum (v ++ s) xs (n+4)
>> _ -> error "asdf"
Cheers,
Bastian
------------------------------
Message: 4
Date: Sun, 07 Nov 2010 12:16:19 +0900
From: Yasuyuki Ogawa <[email protected]>
Subject: Re: [Haskell-beginners] IO loops with tail call
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hi Brent,
(2010/11/07 4:26), Brent Yorgey wrote:
> However, the real answer is: don't worry about it! Because of
> Haskell's lazy evaluation, the notion of "tail call" is not very
> important. And even if it were, you still shouldn't worry about it:
> just write your Haskell programs in the most natural, beautiful style
> you can think of. Maybe at some point down the road you will have
> to start worrying about optimization. But you should put it off as
> long as possible.
Thank you for your helpful advice. In fact, I was wondering
how coding styles affect optimization! I'll forget it a while.
--------------------------------------
Get the new Internet Explorer 8 optimized for Yahoo! JAPAN
http://pr.mail.yahoo.co.jp/ie8/
------------------------------
Message: 5
Date: Sun, 7 Nov 2010 16:47:27 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] editing a list
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
What the original author appears to want is "string rewriting".
Dave Bayer had a nice implementation in this thread...
http://www.haskell.org/pipermail/beginners/2010-February/003399.html
His question was actually about something else, but the continuation
of the thread illuminates his technique, see my reply and the messages
following it up:
http://www.haskell.org/pipermail/beginners/2010-February/003433.html
String rewriting is not particularly straight-forward in Haskell
because you are consuming the input string and generating output at
"different speeds" so using direct recursion and pattern matching
makes for monolithic code. By "different speeds" I mean you might want
to look at one or several characters in the input to match a token,
and produce zero, one or many characters as output at each rewrite
step.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 29, Issue 9
****************************************