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: Recursive Let (Brent Yorgey)
2. Re: Re: A Comparison of Haskell and Scheme (Albert Krewinkel)
3. Re: Recursive Let (Tom Poliquin)
4. Re: Recursive Let (Brent Yorgey)
5. Re: Recursive Let (Thomas Davie)
6. Deforesting binary tree operations? (Neal Alexander)
7. permuting a list (Jan Snajder)
8. Re: permuting a list (Thomas Davie)
9. Re: permuting a list (Patrick LeBoutillier)
----------------------------------------------------------------------
Message: 1
Date: Tue, 10 Feb 2009 10:57:56 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Recursive Let
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Mon, Feb 09, 2009 at 05:43:03PM -0800, Tom Poliquin wrote:
>
>
> 1) How does recursion happen?
>
> Being an ex-Schemer I recalled that let x = 3
> get translated into something like
>
> (lambda (x) ... ) 3
>
> So now there's a function involved. It's clear that b:d is
>
> (cons b d)
>
> another function. So with appropriate plumbing
> I could see the thing recurses but the Haskell viewpoint
> eludes me.
In Haskell, thinking of let expressions as being translated into
lambda expressions is not very helpful, precisely because of the
special ability to have recursive let bindings. In Haskell it is
perfectly OK to have something like
let x = 1:y
y = 0:x
in ...
but it is not clear how this would get translated into function
application (which would come first?). It's better just to think of
let as a special, primitive construct.
>
> 2) How do things get started?
>
> It seems that Haskell could figure out that
> 'd' is a list. If an uninitialized (undefined?)
> list contains [] then things are reasonably
> straightforward ..
An "uninitialized" list does not contain []. I think perhaps your use
of the terms "uninitialized/undefined" might betray an imperative
mindset (?); in any case these are not the right words to use, since
they give an incorrect picture of what is going on.
Here's what actually happens: as a first example, let's consider the
let-binding
let x = 1:x
in ...
What happens here is that x is bound to a closure or 'thunk'
(suspended computation) which, *when needed*, will evaluate to 1:x.
This is laziness at work. x is not 'uninitialized'; it is perfectly
well initialized to this thunk. It is definitely not equal to []; at
this point the runtime doesn't know anything about x other than the
fact that it is a list, and that there is a thunk which may be
evaluated if and when the value of x is actually needed. If you don't
use x anywhere in the ..., nothing will ever happen and the thunk will
eventually get garbage collected (in fact, it's likely that the
compiler would optimize x away and it would never be in memory at
all).
But suppose the value of x is needed (that is, some code
pattern-matches on x). Then the thunk will be evaluated just far
enough to allow the pattern-match: in particular, x will now be a list
with first element 1, and remainder of the list... another thunk. At
this point x is not [1]; it is [1:...] where the ... represents
another thunk which will evaluate to x. This process repeats as more
elements of x are needed, with each thunk evaluating just far enough
to allow the necessary pattern-matches, and suspending the remainder
of computation in another thunk.
Now, let's look at your example:
let (c,d) = (d,b:d)
Of course, c and d will both be initialized to thunks which will
evaluate to lists as needed. It's important to realize that from a
semantic point of view, b, c, and d never change. They always
represent the same, unchanging values, as defined by this let
statement; it's just that operationally, only part of those values may
be actually evaluated, as needed.
If b has the value 7, then d = 7:d, which means d = 7:7:d, which means
d = 7:7:7:d, and so on, and the runtime will expand d out as far as
needed (in this case, 10 elements). You really can think of d as
*being* an infinite list of 7's, only part of which is evaluated.
> This is all fine. The only thing that subconsciously
> nags me is that we appear to 'return' each time which
> would imply that we would leave the closure causing 'd'
> to be undefined again.
One way to think about it is that we only 'return' once: when
tracePlus 7 is evaluated, it returns, once and for all, a value 'c',
the evaluation of which happens to be suspended; it will be evaluated
further as needed. Of course, if you want, you can indeed think of
execution jumping back and forth between main and tracePlus as c is
evaluated bit by bit, but I think this view is unhelpful, as it
suggests procedure calls in an imperative language, where local
variables such as 'd' would indeed go out of scope each time tracePlus
'exited'. Instead, think of tracePlus as returning a closure, which
packages up the values of b, c, and d; it is this closure which is
then evaluated incrementally as execution continues.
> Back to the undefined list ... if it's *not* an
> [] and has something to do with bottom ( _|_ )
> then my eyes glaze over and I have to go watch a
> Woody Allen movie to reset.
A truly _undefined_ list is indeed _|_, and not []. [] is quite
defined; it is the list with no elements. _|_ just means 'the
completely undefined value'. However, as I hope I have made clear
above, the c and d in your example are neither [] nor undefined, so
this is immaterial.
There is much more to say on the topic, and doubtless there are places
where I've told some small fibs because the truth is more
complicated. But hopefully this helps provide a useful way to
understand things.
-Brent
------------------------------
Message: 2
Date: Tue, 10 Feb 2009 08:32:37 -0800
From: Albert Krewinkel <[email protected]>
Subject: Re: [Haskell-beginners] Re: A Comparison of Haskell and
Scheme
To: Benjamin L.Russell <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Benjamin L.Russell <[email protected]> writes:
> On Tue, 10 Feb 2009 19:03:31 +0900, Benjamin L.Russell
> <[email protected]> wrote:
>
>>There is also a related thread on this issue:
>>
>>Explanation of macros; Haskell macros
>>http://mail.python.org/pipermail/python-list/2003-October/228339.html
>>
>>The above-referenced paper also references the following related paper
>>discussing this topic in more detail:
>>
>>Template Meta-programming for Haskell
>>by Tim Sheard and Simon Peyton Jones
>>http://www.haskell.org/th/papers/meta-haskell.ps
>
> Correction: Please substitute "thread" for "paper" in the
> above-quoted sentence starting with "The above-referenced paper...."
>
> Apologies.
>
> -- Benjamin L. Russell
Those are great resources! Thanks a lot!
Albert
------------------------------
Message: 3
Date: Tue, 10 Feb 2009 23:37:14 -0800
From: Tom Poliquin <[email protected]>
Subject: Re: [Haskell-beginners] Recursive Let
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Tuesday 10 February 2009 07:57, Brent Yorgey wrote:
> On Mon, Feb 09, 2009 at 05:43:03PM -0800, Tom Poliquin wrote:
> tracePlus b = let (c,d) = (d,b:d)
> in c
> main = do
> w <- return $ take 10 $ tracePlus 7
> print w
>
> > 1) How does recursion happen?
> In Haskell, thinking of let expressions as being translated into
> lambda expressions is not very helpful, precisely because of the
> special ability to have recursive let bindings. In Haskell it is
> perfectly OK to have something like
>
> let x = 1:y
> y = 0:x
> in ...
>
> but it is not clear how this would get translated into function
> application (which would come first?). It's better just to think of
> let as a special, primitive construct.
Ah, this is what I needed, a mental model that actually fits
what's happening.
> > 2) How do things get started?
> An "uninitialized" list does not contain []. I think perhaps your use
> of the terms "uninitialized/undefined" might betray an imperative
> mindset (?)
I've been doing FP for about 3 years (and imperative for 30)
I guess old habits are hard to break :-) I went from Scheme
to ML and now Haskell and it seems like every day there's
something new for me to try to wrap my head around.
(Is category theory next ??!! ... into the rabbit hole .. no
pejorative intent)
> Here's what actually happens: as a first example, let's consider the
> let-binding
>
> let x = 1:x
> in ...
>
> What happens here is that x is bound to a closure or 'thunk'
> (suspended computation) which, *when needed*, will evaluate to 1:x.
> This is laziness at work. x is not 'uninitialized'; it is perfectly
> well initialized to this thunk.
Great point. It seems like laziness is the major part of my misunderstanding.
Thinking about thunks will help a lot.
> Now, let's look at your example:
>
> let (c,d) = (d,b:d)
>
> Of course, c and d will both be initialized to thunks which will
> evaluate to lists as needed. It's important to realize that from a
> semantic point of view, b, c, and d never change. They always
> represent the same, unchanging values, as defined by this let
> statement; it's just that operationally, only part of those values may
> be actually evaluated, as needed.
Ok, this clears things up a lot ! I just need to internalize it.
> A truly _undefined_ list is indeed _|_, and not [].
> However, as I hope I have made clear
> above, the c and d in your example are neither [] nor undefined, so
> this is immaterial.
Good. I'm not ready for _|_ yet .. :-)
> There is much more to say on the topic, and doubtless there are places
> where I've told some small fibs because the truth is more
> complicated. But hopefully this helps provide a useful way to
> understand things.
>
> -Brent
Yes it does, and you're right I'm probably not ready for the 'truth' yet :-)
Thanks for the very detailed reply. It was extremely helpful!
Tom
------------------------------
Message: 4
Date: Wed, 11 Feb 2009 03:29:24 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Recursive Let
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>
> Good. I'm not ready for _|_ yet .. :-)
There's actually nothing all that difficult about _|_; it is the value
of divergent computations--i.e. infinite recursion which never
actually produces any data. We usually also say that anything which
results in a run-time error is _|_. For example, each of the following
is _|_:
undefined
error "blarg"
let x = x in x
let y = y + 1 in y
> Thanks for the very detailed reply. It was extremely helpful!
Glad to hear it!
-Brent
------------------------------
Message: 5
Date: Wed, 11 Feb 2009 09:34:54 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] Recursive Let
To: Brent Yorgey <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 11 Feb 2009, at 09:29, Brent Yorgey wrote:
>>
>> Good. I'm not ready for _|_ yet .. :-)
>
> There's actually nothing all that difficult about _|_; it is the value
> of divergent computations--i.e. infinite recursion which never
> actually produces any data. We usually also say that anything which
> results in a run-time error is _|_. For example, each of the following
> is _|_:
>
> undefined
> error "blarg"
> let x = x in x
> let y = y + 1 in y
Note though that it's not the value of divergent computations, but
instead of divergent computations that also never produce any output.
For example, this divergent computation is not _|_, because it
produces values:
ones = 1 : ones
More precisely, in haskell bottom is a value in every type which we
can give no information about at all.
In mathematics, bottom is a value which contains the *least*
information of any value in the set, this is true in Haskell also, but
also guarenteed by the fact that types are extended to include a
special "I know nothing at all" value.
Bob
------------------------------
Message: 6
Date: Thu, 12 Feb 2009 00:44:08 -0800
From: Neal Alexander <[email protected]>
Subject: [Haskell-beginners] Deforesting binary tree operations?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Is it possible to deforest something like this?
data Matrix a = Scalar a
| Matrix (Matrix a,Matrix a,Matrix a,Matrix a)
(*) (Matrix (a11,a12,a21,a22)) (Matrix (b11,b12,b21,b22)) =
Matrix ( (a11 * b11) + (a12 * b21),
(a11 * b12) + (a12 * b22),
(a21 * b11) + (a22 * b21),
(a21 * b12) + (a22 * b22) )
(*) (Scalar a) (Scalar b) = Scalar (a * b)
------------------------------
Message: 7
Date: Thu, 12 Feb 2009 10:20:32 +0100
From: Jan Snajder <[email protected]>
Subject: [Haskell-beginners] permuting a list
To: [email protected]
Message-ID: <1234430432.5888.23.ca...@arjuna>
Content-Type: text/plain
Hi!
I'm trying to write a list permutation function, and there is in fact a
nice explanation of how to do it here:
http://sneakymustard.com/2008/12/23/shuffling-in-haskell
But for the start I wanted to keep things simple and avoid monad
transformers (since I'm not into this yet). Instead, I'd like to write a
function of type:
> permute :: [a] -> IO [a]
and so this is what I did:
> permute xs = do
> let n = length xs - 1
> arr0 <- newListArray (0, n) xs
> arr <- foldM swap arr0 [n..1]
> getElems arr
> where swap arr n = do
> x <- readArray arr n
> r <- randomRIO (0, n)
> y <- readArray arr r
> writeArray arr n y
> writeArray arr r x
> return arr
Unfortunately, what I get is:
> permute :: (MArray a1 a IO) => [a] -> IO [a]
and so when I try to apply this function:
> permute [1,2,3]
this is what I get:
<interactive>:1:0:
No instance for (MArray a1 t IO)
arising from a use of `permute' at <interactive>:1:0-14
Possible fix: add an instance declaration for (MArray a1 t IO)
In the expression: permute [1, 2, 3]
In the definition of `it': it = permute [1, 2, 3]
How can I fix this?
Thanx,
jan
------------------------------
Message: 8
Date: Thu, 12 Feb 2009 11:24:25 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] permuting a list
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 12 Feb 2009, at 10:20, Jan Snajder wrote:
> Hi!
>
> I'm trying to write a list permutation function, and there is in
> fact a
> nice explanation of how to do it here:
> http://sneakymustard.com/2008/12/23/shuffling-in-haskell
>
> But for the start I wanted to keep things simple and avoid monad
> transformers (since I'm not into this yet). Instead, I'd like to
> write a
> function of type:
>
>> permute :: [a] -> IO [a]
o.O
Why not keep things simple and just write a pure function?
permute :: [a] -> [[a]]
permute xs = [s:ps | (s,ss) <- select xs, ps <- permute ss]
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(s,x:ss) | (s,ss) <- select xs]
Bob
------------------------------
Message: 9
Date: Thu, 12 Feb 2009 09:53:43 -0500
From: Patrick LeBoutillier <[email protected]>
Subject: Re: [Haskell-beginners] permuting a list
To: Thomas Davie <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi,
>
> Why not keep things simple and just write a pure function?
>
> permute :: [a] -> [[a]]
> permute xs = [s:ps | (s,ss) <- select xs, ps <- permute ss]
>
> select :: [a] -> [(a,[a])]
> select [] = []
> select (x:xs) = (x,xs) : [(s,x:ss) | (s,ss) <- select xs]
When I run this in ghci I always get an empty list:
[patri...@fc9i386 haskell]$ ghci permute.hs
GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( permute.hs, interpreted )
Ok, modules loaded: Main.
*Main> permute [1,2,3]
[]
Am i missing something?
Patrick
>
> Bob
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 9
***************************************
