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: Question about data structures (Russ Abbott)
2. Re: Pointfree expeiments (Stephen Tetley)
3. Re: Pointfree expeiments (Paul Sargent)
4. Re: Pointfree expeiments (Ozgur Akgun)
5. Re: Pointfree expeiments (Daniel Schoepe)
----------------------------------------------------------------------
Message: 1
Date: Wed, 24 Nov 2010 18:58:58 -0800
From: Russ Abbott <[email protected]>
Subject: Re: [Haskell-beginners] Question about data structures
To: Daniel Fischer <[email protected]>, matthew coolbeth
<[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
My previous two messages suggest a Haskell coding principle: distinguish
between fixed and (quasi-)mutable data structures. (I know values don't
change, but I hope you understand what I mean. The cage and the cell in my
previous example are quasi-mutable. They are conceptually mutable in the
context of the problem.) The fixed data structures can be organized any way
one wants. The quasi-/conceptually-mutable elements should be referred to
symbolically and stored in a Map. The maps themselves should be stored at a
global level of the system's data structure so that it is easy to replace
them when values change.
*
-- Russ *
On Wed, Nov 24, 2010 at 5:54 PM, Russ Abbott <[email protected]> wrote:
> Actually using a Map does solve the problem. The Map has to be kept at the
> level of the Tree rather than have each leaf node point to it. So instead
> of just a Tree one has, say (Map, Tree). Then when one wants to change the
> property of something associated with a leaf node, one can just change the
> map. The Tree is unchanged.
> *
> -- Russ*
> ***
> *
> **
>
>
> On Wed, Nov 24, 2010 at 2:02 PM, Russ Abbott <[email protected]>wrote:
>
>> OK. So putting a Map at Leaf nodes doesn't solve the problem.
>> (Apparently I haven't been able to communicate what I see as the problem.)
>>
>> The problem that I'm trying to get to is the need to write excessive code
>> for something that would require a lot less code in an OO world. It's not a
>> matter of execution time or space. It's a matter of the amount of code one
>> is required to write.
>> *
>> -- Russ *
>>
>>
>>
>> On Wed, Nov 24, 2010 at 1:52 PM, Daniel Fischer <[email protected]
>> > wrote:
>>
>>> On Wednesday 24 November 2010 22:12:37, Russ Abbott wrote:
>>> > Cool. I wasn't aware of that notation. It doesn't quite get to the
>>> > issue though.
>>> >
>>> > The problem I'm concerned about is the need to define y in the first
>>> > place. If one is chasing through a data structure and finds a need to
>>> > change something buried within it, it seems necessary to rebuild
>>> > everything that includes the changed thing.
>>>
>>> In general, values are immutable, so you can't "change something buried
>>> within it". You have to build a new value containing some of the old
>>> stuff
>>> and a new part. Building the new value usually consists mostly of copying
>>> a
>>> couple of pointers (plus building the new part of course), so isn't too
>>> expensive normally.
>>>
>>> You can have mutable values in the IO or (ST s) monads, if you need them.
>>>
>>> > That is, I can't change a
>>> > component of somethingNew without creating y. The point is there's
>>> > nothing about x that changed,
>>>
>>> The thing with the changed component is not x anymore.
>>>
>>> > and there may be nothing about (var1 x)
>>> > that changed, and there may be nothing about var11 . var1 $ x that
>>> > changed, etc. Yet one is apparently forced to keep track of and
>>> > reconstruct all those elements.
>>>
>>> The compiler takes care of that.
>>>
>>> >
>>> > Another example is to imagine a Tree in which the leaves contain
>>> > "objects." If I want to change a property of one of those leaf objects,
>>>
>>> You can't in general, the thing with a different property is a different
>>> object.
>>>
>>> > I am forced to rebuild all the ancestor nodes of that leaf down to
>>> > rebuilding the root.
>>>
>>> Yes (well, not you, the compiler does it), except if your tree contains
>>> mutable objects (IORefs/STRefs for example).
>>>
>>> >
>>> > One way to avoid that is for the leaves to refer to their objects
>>> > through a Map. Then changing a leaf object requires only that the value
>>> > associated with key represented by the leaf be (re-)inserted into the
>>> > Map. The Tree itself need not change at all.
>>>
>>> Oh, it will. If you change a Map, you get a new one, thus you get a new
>>> tree containing the new Map.
>>>
>>> >
>>> > But that trick isn't always available. In the example we are talking
>>> > about we can't make a Map where they keys are the instance variable
>>> > names and the values are their values. That would seem to do the job,
>>> > but since the values are of different types, we can't create such a
>>> Map.
>>> >
>>> > So now what?
>>>
>>> Well, what's the problem with the compiler copying some nodes?
>>> Normally, that doesn't cost very much performance, if it does in your
>>> case,
>>> we'd need to know more to suggest the best way to go.
>>>
>>> > *
>>> > -- Russ *
>>> >
>>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20101124/ff71826f/attachment-0001.html
------------------------------
Message: 2
Date: Thu, 25 Nov 2010 09:12:59 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] Pointfree expeiments
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On 25 November 2010 01:44, Paul Sargent <[email protected]> wrote:
[SNIP]
>
> I'm aware that 'ap' is related the liftM, but what is this monad, and why are
> we working in a monad at all?
>
> ...and surely this isn't the same as the original code as we now have a
> different type signature?_______________________________________________
Its the Reader monad.
The Reader monad introduces a "static argument" into the computation.
The code is equivalent to the original - if you want you can declare
it as a binding without generalizing it to Monad:
Prelude Control.Monad> let f = ap (+) id :: Num a => a -> a
Pointfree is presumably introducing it because it can't find
elementary definitions that are only functional types - the
combinators in the Haskell Prelude and Data.Function are perhaps a
little meagre. In one stroke it is a use of the 'w' combinator:
f :: Num a => a -> a
f = w (+)
-- | W combinator - warbler - elementary duplicator.
w :: (r1 -> r1 -> ans) -> r1 -> ans
w f x = f x x
Monadic ap for the Reader monad corresponds to the Starling 's'
combinator, so it is also:
g :: Num a => a -> a
g = starling (+) id
Again, Pointfree doesn't have starling available:
starling :: (r1 -> a -> ans) -> (r1 -> a) -> r1 -> ans
starling f g x = f x (g x)
------------------------------
Message: 3
Date: Thu, 25 Nov 2010 10:55:39 +0000
From: Paul Sargent <[email protected]>
Subject: Re: [Haskell-beginners] Pointfree expeiments
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Thanks Stephen,
On 25 Nov 2010, at 09:12, Stephen Tetley wrote:
> On 25 November 2010 01:44, Paul Sargent <[email protected]> wrote:
> [SNIP]
>
>>
>> I'm aware that 'ap' is related the liftM, but what is this monad, and why
>> are we working in a monad at all?
>>
>> ...and surely this isn't the same as the original code as we now have a
>> different type signature?_______________________________________________
>
> Its the Reader monad.
>
> [...]
> Pointfree is presumably introducing it because it can't find
> elementary definitions that are only functional types [...]
> In one stroke it is a use of the 'w' combinator:
> -- | W combinator - warbler - elementary duplicator.
> w :: (r1 -> r1 -> ans) -> r1 -> ans
> w f x = f x x
> Monadic ap for the Reader monad corresponds to the Starling 's'
> combinator:
> starling :: (r1 -> a -> ans) -> (r1 -> a) -> r1 -> ans
> starling f g x = f x (g x)
The Starling and Warbler combinators make perfect sense to me. I'm still trying
to see how ap in the Reader Monad is equivalent to Starling. I think this is
exposing some holes in my Haskell knowledge, so I'm using it as a learning
exercise.
We use them in the same way, and we're saying they're equivalent:
let f x = starling (+) id
let g x = ap (+) id
Yet, they have quite different type signatures.
starling :: (r1 -> a -> ans) -> (r1 -> a) -> r1 -> ans
ap :: (Monad m) => m (a -> b) -> m a -> m b
So, my first question is what makes haskell choose the Reader monad in this
case?
Secondly, (+) is a function of two arguments, and id a function of one. This
binds naturally with starling, but not apparently with ap. Apparently ap wants
a single argument function within a monad as it's first argument, so to me (+)
shouldn't satisfy. I suspect the answer to this has something to do with my
first question.
Digging a little deeper, I decided to look at the definition of ap:
ap = liftM2 id
liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
liftM2 makes sense to me, but again we seem to have a mismatch of types. liftM2
wants a two argument function for it's first argument, but ap provides id. I'm
finding myself tumbling further and further down the rabbit hole.
Paul
------------------------------
Message: 4
Date: Thu, 25 Nov 2010 11:14:41 +0000
From: Ozgur Akgun <[email protected]>
Subject: Re: [Haskell-beginners] Pointfree expeiments
To: Paul Sargent <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="utf-8"
I don't know whether this is related or not, but I have the following
somewhere in my code:
-- the following is apparently eqivalent to (\ i -> foo (bar i) i).
-- pointfree suggests so. i don't understand why.
(foo =<< bar)
Is this a similar situation?
--
Ozgur Akgun
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20101125/550c337a/attachment-0001.html
------------------------------
Message: 5
Date: Thu, 25 Nov 2010 13:40:52 +0100
From: Daniel Schoepe <[email protected]>
Subject: [Haskell-beginners] Re: Pointfree expeiments
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain
Paul Sargent <[email protected]> writes:
> Digging a little deeper, I decided to look at the definition of ap:
>
> ap = liftM2 id
>
> liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
> liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
>
> liftM2 makes sense to me, but again we seem to have a mismatch of types.
> liftM2 wants a two argument function for it's first argument, but ap provides
> id. I'm finding myself tumbling further and further down the rabbit hole.
>
id has type a -> a, so if you "instantiate" a to `a2 -> r', you get:
id :: (a2 -> r) -> (a2 -> r)
Since -> is right-associative this is the same as:
id :: (a2 -> r) -> a2 -> r
So that's how id can be seen as a two-argument function in this
case. That results in liftM2 id having the type:
liftM2 id :: (Monad m) => m (a2 -> r) -> m a2 -> m r
If you now insert the Reader monad for m, you get:
liftM2 id :: (s -> a2 -> r) -> (s -> a2) -> (s -> r)
So appying (liftM2 id), which is ap, to (+), causes s, a2 and r to be
the same type, since (+) has type (Num a) => a -> a -> a.
liftM2 id (+) :: Num a => (a -> a) -> a -> a
If you then apply that to id, as in ap (+) id, you get:
ap (+) id = liftM2 id (+) id :: Num a => a -> a
So this explains the type, and if you then expand the definitions of
liftM2 and >>= and return for the Reader monad, you will see that this
corresponds to \x -> x + x.
Regards,
Daniel
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 29, Issue 38
*****************************************
