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: Hudak state emulation discussion - can you give me some
idea? (Will Ness)
2. Re: Understanding recursion in Haskell. (Thomas Davie)
3. Re: Understanding recursion in Haskell. (Will Ness)
4. Re: Advice wanted on parallel processing (Colin Paul Adams)
5. Re: Re: folds again -- myCycle (Daniel Fischer)
6. Re: Advice wanted on parallel processing (Daniel Fischer)
7. Re: folds again -- myCycle (Will Ness)
8. Re: folds again -- myCycle (Will Ness)
9. Re: folds again -- myCycle (Will Ness)
----------------------------------------------------------------------
Message: 1
Date: Wed, 18 Mar 2009 15:36:06 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: Hudak state emulation discussion -
can you give me some idea?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Will Ness <will_n48 <at> yahoo.com> writes:
> infixl 8 +'
> infix 8 <'
> infix 7 :=
> infixl 6 ; -- infixr is good too
>
> (p; q) s = q (p s) -- (;) = CB -- flip (.)
> (x:=f) s = x s (f s) -- (:=) = S
> goto f s = f s -- id = I
> (f+'g) s = f s + g s
> (f<'g) s = f s < g s
> if' p c s = if (p s) then (c s) else s
> x' (a,b) = a
> i' (a,b) = b
>
Er, forgot to include the two state updaters of the article,
x (a,b) v = (v,b)
i (a,b) v = (a,v)
------------------------------
Message: 2
Date: Wed, 18 Mar 2009 16:39:47 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
To: Zachary Turner <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 18 Mar 2009, at 16:32, Zachary Turner wrote:
> A few others have given more complete walkthroughs / traces of the
> executions, but just to add a little. When it finally "clicked"
> with me and recursion became easier to understand, it was when I
> stopped trying to think about the entire execution chain. For
> example, let's say I run a ticket resale (scalping) shop and someone
> calls me and says "hey I need two tickets for the show this
> saturday." I tell the guy sure no problem, I'll call you back in 2
> hours. But actually I don't have the tickets, so I call one of my
> connections. Unfortunately, he doesn't have the tickets either so
> this process ends up repeating for a while. When I talk to my
> connection on the phone I don't think "ok he's going to call John,
> and John's probably going to call William, and then William might
> call Frank, etc". I just think "he's either going to call me back
> and say yes or no, regardless of how he arrives at that answer".
> That's the key to recursion.
This, and the fact that Frank does not call you looking for tickets
(i.e. we must always make some progress).
Bob
------------------------------
Message: 3
Date: Wed, 18 Mar 2009 15:47:34 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: Understanding recursion in Haskell.
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Zachary Turner <divisortheory <at> gmail.com> writes:
> The entire chain of stuff that happens as a result of "the max of everything
else", isn't important. The important thing is that IF you have the first
element, and IF you have the max of everything else, then the max of the whole
list is the greater of those two items.Â
IOW, to add a bit to your vivid description, a key to understanding recursion
is learning to let go. It's zen, really. :)
It's learning to rely on the veracity of sub-results and just to combine them
in a proper correctness-preserving fashion. It's about design by contract, and
keeping invariants.
------------------------------
Message: 4
Date: Wed, 18 Mar 2009 15:49:25 +0000
From: Colin Paul Adams <[email protected]>
Subject: [Haskell-beginners] Re: Advice wanted on parallel processing
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>>>>> "Daniel" == Daniel Fischer <[email protected]> writes:
Daniel> If e.g.
Daniel> data Move = Move {from :: Position, to :: Position}
Daniel> , the instance would be
Daniel> instance NFData Move where rnf (Move f t) = rnf f `seq`
Daniel> rnf t `seq` ()
Daniel> That might require NFData instances for Position and its
Daniel> components, but specifying these should be automatic.
<switched to beginners list>
Move is somewhat more complicated than that, but it comes down to
specifying instances for
data Piece_colour
= Black
| White
and
data Piece_type
= Lance
| Reverse_chariot
| Side_mover
| Vertical_mover
| White_horse
| Rook
... many more
which I'm not sure how to do. I tried added a deriving clause, but the
compiler complains:
Can't make a derived instance of `NFData Piece_colour'
(`NFData' is not a derivable class)
In the data type declaration for `Piece_colour'
here I don't have and fields to force.
--
Colin Adams
Preston Lancashire
------------------------------
Message: 5
Date: Wed, 18 Mar 2009 17:03:06 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: folds again -- myCycle
To: Will Ness <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Am Mittwoch, 18. März 2009 16:14 schrieb Will Ness:
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:
> > > Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
> >
> > wrote:
> > > > > myCycle xs = ys where ys = foldr (:) ys xs
> >
> > Of course a matter of personal preference, but I tend to prefer where
> > clauses, too, in general. However, my preferred layout is
> >
> > some code
> > where
> > local declarations
> >
> > I deeply loathe not having the where on a separate line :-/
>
> Will try not to offend in the future. :)
Very kind of you. But stick to your own style, I can live with loathing the
layout of some code :-)
>
> > AFAIK,
> >
> > [let and where versions of myCycle] are compiled to exactly the same
> > code.
>
> since there are no guards there with shared variables, I guess.
No, that doesn't matter. GHC-core has no where, only let, so all where clauses
must be rewritten to use let.
>
> > What matters is whether you give a name to the result to get it shared or
> > not.
>
> I was hoping GHC is smarter than that in finding shared expressions. Is it
> what's called deforestation?
Sorry, don't know about that, but I think not,
common-subexpression-elimination sounds more like it. But I'm guessing here.
>
> Also, one can imagine this rewrite to be arrived at automagically by a
> compiler:
>
> sum $ take m $ cycle [1..k]
>
> | n > 0 = x*n+y
>
> where
> (n,r) = quotRem m k
> x = sum [1..k]
> y = sum [1..r]
>
> Any human is certainly capable of seen this almost immediately, presented
> with the big k's and huge m's. It's automagical. :)
But it's too much of a special case to have a special rule for it in the
compiler code.
Humans are much less principled and can thus spot a greater variety of
patterns (but they are also better in overlooking such patterns).
>
> Cheers,
>
------------------------------
Message: 6
Date: Wed, 18 Mar 2009 17:11:25 +0100
From: Daniel Fischer <[email protected]>
Subject: [Haskell-beginners] Re: Advice wanted on parallel processing
To: Colin Paul Adams <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Mittwoch, 18. März 2009 16:49 schrieb Colin Paul Adams:
> >>>>> "Daniel" == Daniel Fischer <[email protected]> writes:
>
> Daniel> If e.g.
>
> Daniel> data Move = Move {from :: Position, to :: Position}
>
> Daniel> , the instance would be
>
> Daniel> instance NFData Move where rnf (Move f t) = rnf f `seq`
> Daniel> rnf t `seq` ()
>
> Daniel> That might require NFData instances for Position and its
> Daniel> components, but specifying these should be automatic.
>
> <switched to beginners list>
>
> Move is somewhat more complicated than that, but it comes down to
> specifying instances for
>
> data Piece_colour
> = Black
>
> | White
>
> and
>
> data Piece_type
> = Lance
>
> | Reverse_chariot
> | Side_mover
> | Vertical_mover
> | White_horse
> | Rook
>
> ... many more
>
> which I'm not sure how to do. I tried added a deriving clause, but the
> compiler complains:
>
> Can't make a derived instance of `NFData Piece_colour'
> (`NFData' is not a derivable class)
> In the data type declaration for `Piece_colour'
For a newtype-wrapper of a type which is an instance of NFData, you can do
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype Thing = T nfdata
deriving NFData
, but for
data Thingummy = ...
you have to write the instance yourself.
>
> here I don't have and fields to force.
For an enumeration like Piece_colour or Piece_type,
instance NFData Piece_colour where
rnf = rwhnf
is all you need, but you don't even necessarily need that, for
data Move = Move {colour :: Piece_colour, typ :: Piece_type, start, end ::
Position}
instance NFData Move where
rnf (Move c t s e) = c `seq` t `seq` rnf s `seq` rnf e
is good.
------------------------------
Message: 7
Date: Wed, 18 Mar 2009 18:00:13 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
> Am Mittwoch, 18. März 2009 16:14 schrieb Will Ness:
> > Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > > Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:
> > > > Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > > > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
> > >
> > > wrote:
> > > > > > myCycle xs = ys where ys = foldr (:) ys xs
> > >
> > > AFAIK,
> > >
> > > [let and where versions of myCycle] are compiled to exactly the same
> > > code.
> >
> > since there are no guards there with shared variables, I guess.
>
> No, that doesn't matter. GHC-core has no where, only let, so all where
clauses
> must be rewritten to use let.
So it must be a more extensive re-write then, for guards, with explicit (case
test of True -> ) etc... :)
> > Also, one can imagine this rewrite to be arrived at automagically by a
> > compiler:
> >
> > sum $ take m $ cycle [1..k]
> >
> > | n > 0 = x*n+y
> >
> > where
> > (n,r) = quotRem m k
> > x = sum [1..k]
> > y = sum [1..r]
> >
> > Any human is certainly capable of seen this almost immediately, presented
> > with the big k's and huge m's. It's automagical. :)
>
> But it's too much of a special case to have a special rule for it in the
> compiler code.
What I was driving at, is having a compiler so smart it'd figure this out on
its own, if needed (i.e. faced with huge m's), not having this specific special
case programmed by a compiler-writer.
> Humans are much less principled and can thus spot a greater variety of
> patterns (but they are also better in overlooking such patterns).
I think it is because we're constantly trying out, unconsciously, various ways
to achieve our goals. It's like a forward-chaining churning in the background,
providing us with currently-known-possibilities sphere, like a cloud of
possibilities around us. Touch the goal with the sphere's surface and - boom! -
we've got ourselves an intuitive solution that's "just there".
Sometimes I think precompilation - pre-evaluation - is the essence of human
creativity. We just invent things in advance, in case we'd ever need them. Same
with dreams. It's just a training engine for us to learn how to run away from a
tiger better, or how to better kill a mammoth. :)
I think it's called speculative eager evaluation.
Cheers,
------------------------------
Message: 8
Date: Wed, 18 Mar 2009 18:10:13 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
> Am Mittwoch, 18. März 2009 16:14 schrieb Will Ness:
> >
> > sum $ take m $ cycle [1..k]
> > | n > 0 = x*n+y
> > where
> > (n,r) = quotRem m k
> > x = sum [1..k]
> > y = sum [1..r]
In fact, the super brilliant deducting compiler would make it
sum $ take m $ cycle [1..k]
| n > 0 = x*n+y
where
(n,r) = quotRem m k
x = k*(k+1)/2
y = r*(r+1)/2
:) :)
------------------------------
Message: 9
Date: Wed, 18 Mar 2009 18:43:58 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
> Am Mittwoch, 18. Maerz 2009 16:14 schrieb Will Ness:
> >
> > sum $ take m $ cycle [1..k]
> > | n > 0 = x*n+y
> > where
> > (n,r) = quotRem m k
> > x = sum [1..k]
> > y = sum [1..r]
In fact, the super-brilliant deducting compiler would make it
sum $ take m $ cycle [1..k]
| n > 0 = x*n+y
where
(n,r) = quotRem m k
x = k*(k+1)/2
y = r*(r+1)/2
:) :)
Now THAT would be a deductive power to behold!
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 22
****************************************
