Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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: oddsFrom3 function (Doug McIlroy)
2. Re: oddsFrom3 function (Rein Henrichs)
3. Re: oddsFrom3 function (akash g)
4. Re: oddsFrom3 function (akash g)
----------------------------------------------------------------------
Message: 1
Date: Mon, 17 Aug 2015 09:17:42 -0400
From: Doug McIlroy <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] oddsFrom3 function
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
> > oddsFrom3 :: [Integer]
> > oddsFrom3 = 3 : map (+2) oddsFrom3
> >
> >
> > Thanks for your help.
>
> Try to expand a few steps of the recursion by hand e.g.:
>
> 3 : (map (+2) (3 : map (+2) (3 : map (+2) ...)))
>
>
> As you can see, the deeper you go more 'map (+2)' are applied to '3'.
Some more ways to describe the program, which may be useful:
As with any recursive function, assume you know the whole series and
then confirm that by verifying the inductive step. In this case
oddsFrom3 = [3,5,7,9,11,...]
map (+2) oddsFrom3 = [5,7,9,11,13,...]
voila
oddsFrom3 = 3 : map (+2) oddsFrom3
Assuming we have the whole series, we see its tail is
computed from the whole by adding 2 to each element.
Notice that we don't actually have to know the values in the
tail in order to write the formula for the tail.
Yet another way to describe the program: the "output" is taken
as "input". This works because the first element of the output,
namely 3, is provided in advance. Each output element can then
be computed before it is needed as input.
In an imperative language this would be done so:
integer oddsFrom3[0:HUGE]
oddsFrom3[0] := 3
for i:=1 to HUGE do
oddsFrom3[i] = oddsFrom3[i-1] + 2
------------------------------
Message: 2
Date: Mon, 17 Aug 2015 16:53:19 +0000
From: Rein Henrichs <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] oddsFrom3 function
Message-ID:
<CAJp6G8zo0dVnrGugA=ehobldf0w8nkgbkezrerdw01er324...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
> The initial version which the OP posted doesn't have a terminal value.
The point is that it doesn't need a terminal value. Infinite lists like
oddsFrom3 and (repeat "foo") and (let xs = 1 : xs) are all perfectly valid
Haskell values.
On Mon, Aug 17, 2015 at 6:17 AM Doug McIlroy <[email protected]> wrote:
> > > oddsFrom3 :: [Integer]
> > > oddsFrom3 = 3 : map (+2) oddsFrom3
> > >
> > >
> > > Thanks for your help.
> >
> > Try to expand a few steps of the recursion by hand e.g.:
> >
> > 3 : (map (+2) (3 : map (+2) (3 : map (+2) ...)))
> >
> >
> > As you can see, the deeper you go more 'map (+2)' are applied to '3'.
>
> Some more ways to describe the program, which may be useful:
>
> As with any recursive function, assume you know the whole series and
> then confirm that by verifying the inductive step. In this case
> oddsFrom3 = [3,5,7,9,11,...]
> map (+2) oddsFrom3 = [5,7,9,11,13,...]
> voila
> oddsFrom3 = 3 : map (+2) oddsFrom3
>
> Assuming we have the whole series, we see its tail is
> computed from the whole by adding 2 to each element.
> Notice that we don't actually have to know the values in the
> tail in order to write the formula for the tail.
>
> Yet another way to describe the program: the "output" is taken
> as "input". This works because the first element of the output,
> namely 3, is provided in advance. Each output element can then
> be computed before it is needed as input.
>
> In an imperative language this would be done so:
> integer oddsFrom3[0:HUGE]
> oddsFrom3[0] := 3
> for i:=1 to HUGE do
> oddsFrom3[i] = oddsFrom3[i-1] + 2
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150817/58ff4a04/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 17 Aug 2015 22:57:24 +0530
From: akash g <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] oddsFrom3 function
Message-ID:
<CALiga_e2hXDKcdHrnE=wy6FQy9W2x_DFkwEF-4yL73mP5GgP=g...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
@Rein:
Perhaps I should have been a bit more clear. There is no way to get a
terminal value from said function.
oddsFrom3 :: [Integer]
oddsFrom3 = map (+2) oddsFrom3
Try a head for it perhaps.
oddsFrom3 = map (+2) oddsFrom3
<=> ((head oddsFrom3) + 2) : map (+2) ((tail oddsFrom3) + 2)
<=> ((head (map (+2) oddsFrom3) + 2) : map (+2) ((tail oddsFrom3) + 2)
Sure, it doesn't hang until you try to evaluate this (in lazy language
evaluators). However, for any inductive structure, there needs to be a
(well any finite number of terminals) terminal (base case) which can be
reached from the starting state in a finite amount of computational
(condition for termination). Type sigs don't/can't guarantee termination.
If they don't have a terminal value, you'll never get to the bottom (bad
pun intended) of it.
Take an infinite list as an example.
x a = a : x a
Here, one branch of the tree (representing the list as a highly unbalanced
tree where every left branch is of depth one at any given point). If such
a structure is not present, you can never compute it to a value and you'll
have to infinitely recurse.
Try x a = x a ++ x a
And think of the getting the head from this. You're stuck in an infinite
loop.
You may also think of the above as a small BNF and try to see if
termination is possible from the start state. A vaguely intuitive way of
looking at it for me, but meh, I might be missing something.
On Mon, Aug 17, 2015 at 10:23 PM, Rein Henrichs <[email protected]>
wrote:
> > The initial version which the OP posted doesn't have a terminal value.
>
> The point is that it doesn't need a terminal value. Infinite lists like
> oddsFrom3 and (repeat "foo") and (let xs = 1 : xs) are all perfectly valid
> Haskell values.
>
> On Mon, Aug 17, 2015 at 6:17 AM Doug McIlroy <[email protected]>
> wrote:
>
>> > > oddsFrom3 :: [Integer]
>> > > oddsFrom3 = 3 : map (+2) oddsFrom3
>> > >
>> > >
>> > > Thanks for your help.
>> >
>> > Try to expand a few steps of the recursion by hand e.g.:
>> >
>> > 3 : (map (+2) (3 : map (+2) (3 : map (+2) ...)))
>> >
>> >
>> > As you can see, the deeper you go more 'map (+2)' are applied to '3'.
>>
>> Some more ways to describe the program, which may be useful:
>>
>> As with any recursive function, assume you know the whole series and
>> then confirm that by verifying the inductive step. In this case
>> oddsFrom3 = [3,5,7,9,11,...]
>> map (+2) oddsFrom3 = [5,7,9,11,13,...]
>> voila
>> oddsFrom3 = 3 : map (+2) oddsFrom3
>>
>> Assuming we have the whole series, we see its tail is
>> computed from the whole by adding 2 to each element.
>> Notice that we don't actually have to know the values in the
>> tail in order to write the formula for the tail.
>>
>> Yet another way to describe the program: the "output" is taken
>> as "input". This works because the first element of the output,
>> namely 3, is provided in advance. Each output element can then
>> be computed before it is needed as input.
>>
>> In an imperative language this would be done so:
>> integer oddsFrom3[0:HUGE]
>> oddsFrom3[0] := 3
>> for i:=1 to HUGE do
>> oddsFrom3[i] = oddsFrom3[i-1] + 2
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150817/b3d7c3f0/attachment-0001.html>
------------------------------
Message: 4
Date: Mon, 17 Aug 2015 22:59:51 +0530
From: akash g <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] oddsFrom3 function
Message-ID:
<CALiga_eUA_brqERg3OkYCk59khB9hCTaqe3f91SP=ufurrx...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Oh, it is a valid value (I think I implied this by saying they'll compile
and you can even evaluate). Just not useful in any given scenario (an
inductive structure where you don't have terminals).
On Mon, Aug 17, 2015 at 10:57 PM, akash g <[email protected]> wrote:
> @Rein:
> Perhaps I should have been a bit more clear. There is no way to get a
> terminal value from said function.
>
>
> oddsFrom3 :: [Integer]
> oddsFrom3 = map (+2) oddsFrom3
>
> Try a head for it perhaps.
>
> oddsFrom3 = map (+2) oddsFrom3
> <=> ((head oddsFrom3) + 2) : map (+2) ((tail oddsFrom3) + 2)
> <=> ((head (map (+2) oddsFrom3) + 2) : map (+2) ((tail oddsFrom3) + 2)
>
> Sure, it doesn't hang until you try to evaluate this (in lazy language
> evaluators). However, for any inductive structure, there needs to be a
> (well any finite number of terminals) terminal (base case) which can be
> reached from the starting state in a finite amount of computational
> (condition for termination). Type sigs don't/can't guarantee termination.
> If they don't have a terminal value, you'll never get to the bottom (bad
> pun intended) of it.
>
>
> Take an infinite list as an example.
>
> x a = a : x a
>
> Here, one branch of the tree (representing the list as a highly unbalanced
> tree where every left branch is of depth one at any given point). If such
> a structure is not present, you can never compute it to a value and you'll
> have to infinitely recurse.
>
> Try x a = x a ++ x a
>
> And think of the getting the head from this. You're stuck in an infinite
> loop.
>
> You may also think of the above as a small BNF and try to see if
> termination is possible from the start state. A vaguely intuitive way of
> looking at it for me, but meh, I might be missing something.
>
>
>
> On Mon, Aug 17, 2015 at 10:23 PM, Rein Henrichs <[email protected]>
> wrote:
>
>> > The initial version which the OP posted doesn't have a terminal value.
>>
>> The point is that it doesn't need a terminal value. Infinite lists like
>> oddsFrom3 and (repeat "foo") and (let xs = 1 : xs) are all perfectly valid
>> Haskell values.
>>
>> On Mon, Aug 17, 2015 at 6:17 AM Doug McIlroy <[email protected]>
>> wrote:
>>
>>> > > oddsFrom3 :: [Integer]
>>> > > oddsFrom3 = 3 : map (+2) oddsFrom3
>>> > >
>>> > >
>>> > > Thanks for your help.
>>> >
>>> > Try to expand a few steps of the recursion by hand e.g.:
>>> >
>>> > 3 : (map (+2) (3 : map (+2) (3 : map (+2) ...)))
>>> >
>>> >
>>> > As you can see, the deeper you go more 'map (+2)' are applied to '3'.
>>>
>>> Some more ways to describe the program, which may be useful:
>>>
>>> As with any recursive function, assume you know the whole series and
>>> then confirm that by verifying the inductive step. In this case
>>> oddsFrom3 = [3,5,7,9,11,...]
>>> map (+2) oddsFrom3 = [5,7,9,11,13,...]
>>> voila
>>> oddsFrom3 = 3 : map (+2) oddsFrom3
>>>
>>> Assuming we have the whole series, we see its tail is
>>> computed from the whole by adding 2 to each element.
>>> Notice that we don't actually have to know the values in the
>>> tail in order to write the formula for the tail.
>>>
>>> Yet another way to describe the program: the "output" is taken
>>> as "input". This works because the first element of the output,
>>> namely 3, is provided in advance. Each output element can then
>>> be computed before it is needed as input.
>>>
>>> In an imperative language this would be done so:
>>> integer oddsFrom3[0:HUGE]
>>> oddsFrom3[0] := 3
>>> for i:=1 to HUGE do
>>> oddsFrom3[i] = oddsFrom3[i-1] + 2
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150817/e6917172/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 86, Issue 15
*****************************************
