![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 22/04/2012 8:52 PM, Orchid Win7 v1 wrote:
> On 22/04/2012 08:44 PM, Stephen wrote:
>> On 22/04/2012 6:44 PM, James Holsenback wrote:
>>> hmmmm ... nonads (well that's self explanatory) better yet faux-nads ...
>>> someone who thinks that gotta pair. OK I'll stop now ;-)
>>
>> I think, for everyone's sake, that you had better. ;-)
>
> Christ knows what happens if I ever try to explain group
> homomorphisms... o_O
LOL
And I think, for everyone's sake, that you had better not. ;-)
--
Regards
Stephen
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 4/21/2012 13:24, Warp wrote:
> I try to suggest "is like this?" the answer is "not really".
That's part of the problem. Occasionally there will be relatively simple
concepts that aren't "like" anything else. You just have to learn the concept.
It's like I read someone wrote about quantum computers. Someone asked "can
you give an example of how that quantum computer algorithm would be written
for a normal computer?" And the person said "No. That's the point. If you
could write it for a normal computer, you wouldn't need a quantum computer."
In the case of currying, the simple concept is that a function F that takes
arguments X, Y, and Z, is the same as a function G that takes argument X and
returns a function that takes Y and Z, such that for all X, F(X,Y,Z)
returning G_x(Y,Z) implies G_x(Y,Z) returns the same as F(X,Y,Z). It's a
simple mathematical statement, not "like" anything in an imperative language
that doesn't do currying.
--
Darren New, San Diego CA, USA (PST)
"Oh no! We're out of code juice!"
"Don't panic. There's beans and filters
in the cabinet."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 4/22/2012 9:51, Warp wrote:
> but the values to which they are fixed is determined at runtime rather
> than at compile time.)
You'd wind up having something closer to "objects" with an "invoke" method
(or functors, if I recall the C++ term). It's just that Haskell makes that
automatic, in the same way the new C++ makes class definitions automatic
when you type a lambda expression. Given enough convenience, you get a
qualitative difference.
> There are probably even deeper implications.
In all honesty, currying was created for computer science, not for computer
programming. It was invented so you could prove things about a one-argument
function that returns one value and apply those proofs to functions that
take multiple arguments and return multiple values. I.e., it was invented
for the same reason it was useful to invent UTMs, or to prove that any
2-tape TM can be emulated by a one-tape TM.
--
Darren New, San Diego CA, USA (PST)
"Oh no! We're out of code juice!"
"Don't panic. There's beans and filters
in the cabinet."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 4/22/2012 11:34, Orchid Win7 v1 wrote:
> Oh, so it can capture local variables too? That's even better than I thought...
It can capture values of local variables, or references to non-local (to the
lambda) variables. It doesn't really capture variables.
--
Darren New, San Diego CA, USA (PST)
"Oh no! We're out of code juice!"
"Don't panic. There's beans and filters
in the cabinet."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 4/21/2012 14:37, Orchid Win7 v1 wrote:
> Again, this obviously doesn't actually work in C++, but it makes the example
> code much easier to write.
Note that both of these are perfectly fine in C#. :-)
> Incidentally, since C++ REALLY DOES have a function type (or at least,
> function POINTER type) which can be passed as an argument, it's one of the
> few languages where it ought to be possible to implement a monad "for real".
> I might try it if I get the time.
There are lots of languages that let you can pass a function as an argument.
--
Darren New, San Diego CA, USA (PST)
"Oh no! We're out of code juice!"
"Don't panic. There's beans and filters
in the cabinet."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 23/04/2012 04:51 AM, Darren New wrote:
> On 4/21/2012 14:37, Orchid Win7 v1 wrote:
>> Again, this obviously doesn't actually work in C++, but it makes the
>> example code much easier to write.
>
> Note that both of these are perfectly fine in C#. :-)
I'd be surprised if I just happened to guess the right syntax for it. ;-)
>> Incidentally, since C++ REALLY DOES have a function type (or at least,
>> function POINTER type) which can be passed as an argument, it's one of
>> the
>> few languages where it ought to be possible to implement a monad "for
>> real".
>
> There are lots of languages that let you can pass a function as an
> argument.
Heh. I bet most of them are scripting languages though. :-P
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 22/04/2012 07:19 PM, Warp wrote:
> http://byorgey.files.wordpress.com/2011/05/monad_tutorial.jpg
Coming back to what I said earlier... Monads aren't actually that
complicated. It's just that it's a rather abstract idea, and it's not
really "like" anything else most programmers will be familiar with.
I think the huge profusion of monad tutorials just reinforces the idea that
1. Monads are really, really hard.
2. Monads are incredibly important. (I.e., if you don't understand them,
you can never use Haskell.)
3. Once you understand them, it will fundamentally change your life.
None of these statements are actually true...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Am 23.04.2012 10:05, schrieb Invisible:
>>> Incidentally, since C++ REALLY DOES have a function type (or at least,
>>> function POINTER type) which can be passed as an argument, it's one of
>>> the
>>> few languages where it ought to be possible to implement a monad "for
>>> real".
>>
>> There are lots of languages that let you can pass a function as an
>> argument.
>
> Heh. I bet most of them are scripting languages though. :-P
Meh. Even good old Turbo Pascal had function pointers.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>>> There are lots of languages that let you can pass a function as an
>>> argument.
>>
>> Heh. I bet most of them are scripting languages though. :-P
>
> Meh. Even good old Turbo Pascal had function pointers.
O RLY?
Because, I was actually *looking* for that feature, and couldn't find
it. It would have been quite helpful...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
OK, so "magma" consists of a set S and a binary operator #. The #
operator takes any two elements of S (including the possibility of two
copies of the same element), and yields a new element of S (possibly the
same one you started with).
∀ x, y ∈ S, x # y ∈ S.
The only "rules" as such are picky, hair-splitting ones. Stuff like "x #
y" must have a single, definite value for all possible inputs. (If, for
example, # stands for division, then if y=0, there is no defined result.
If we're working with integers only, 2/3 isn't an integer. And so on.)
A magma isn't especially interesting by itself. However, if we add the
rule that # must be /associative/, then we got a "semigroup".
∀ x, y, z ∈ S, (x # y) # z = x # (y # z).
Already this begins to have interesting mathematical properties. But if
we add a special /identity element/, we get a "monoid".
∃ i ∈ S: ∀ x ∈ S, i # x = x # i = x.
So what are we really saying? We're saying that a monoid is a set of
things that have a procedure for combining them, and that there has to
be a special one where combining it does nothing.
There are many possible examples of this. For example, if S is a set of
numbers and # denotes addition, then 0 is our identity element. (Every
child knows that x + 0 = x.) Less obviously, if # denotes
multiplication, our identity element is 1. (Since 1 * x = x.)
But there are other examples too. If S is the set of all possible text
strings, and # denotes concatenation, then the identity element is the
empty string. (Appending or prepending an empty string does nothing.) If
S is the set of all 1-argument functions [with the same return type as
their argument type], and # denotes function composition, then the
identity FUNCTION is the identity ELEMENT. (Bet you can't work out how
/that/ naming scheme came about. :-P )
If you now take your monoid and give every element a corresponding
/inverse element/, then you have a "group".
∀ x ∈ S, ∃ y ∈ S: x # y = y # x = i.
For example, in the monoid of numbers where # is addition, the inverse
of (say) 5 would be -5. And hence, numbers and addition actually form a
/group/, not just a monoid.
Considering strings, however, there is no string that you can append to
something which "undoes" the act of appending an earlier string. So
strings with concatenation form a monoid, but not a group.
All of this is fascinating, of course, but not directly related to MONADS.
If somebody asks "what is a monad?", the stereotypical response is
"A monad is just a monoid in the category of endofunctors - what's
the problem?"
The problem, obviously, is that if you don't know category theory, this
makes not one shred of sense.
A less abstract way to think about it is this: If you have a value like
x, you can put that inside a "box", which I will denote as [x]. Any
value can be put in a box; in particular, you can put a /box/ in a box,
for example [[x]].
Every /monad/ is also a /functor/. This merely means that there's a
function (usually called "map"):
map :: (x -> y) -> ([x] -> [y])
In other words, it takes a function that works an x-values, and turns it
into a function that works on boxes containing x-values. (And instead of
returning y-values, it now returns boxes containing y-values.) In
summary, it "lifts" a function from working on values, to working on
values in boxes.
The alternative way to think about map is
map :: (x -> y) -> [x] -> [y]
In other words, given a function from x to y, and an x in a box, I will
give you a y in a box.
Either way, there's a way to apply an ordinary function to values in
boxes. Given that, there are two equivalent ways to define a monad. They
both involve a function called "return":
return :: x -> [x]
Return just takes a value and puts it in a box. "Inject" or "insert"
might be a better name, but for some reason we're stuck with "return".
Ho hum.
The other function is either "join" or "bind". One can be defined from
the other - although this is highly non-obvious.
Join is the easy one to understand:
join :: [[x]] -> [x]
It takes a box within a box, and gives you just a box. It removes one
level of boxiness. That's pretty easy to comprehend.
Bind, on the other hand, has the hoopy type signature
bind :: [x] -> (x -> [y]) -> [y]
In other words, given...
- An x in a box.
- A function that wants an x and gives you a y in a box
...I can give you a y in a box.
Notice how the x arrives IN A BOX, but the function expects a value NOT
IN A BOX. So bind has to take a value /out/ of a box. Right? Right??
Actually... no. You can implement it just using join:
bind box_x function = join (map function box_x)
Applying the function to the x inside the [x] yields a result of type
[[y]]. Applying join to that turns it from [[y]] into [y] - the required
result type.
Less obvious still is that join can be defined using bind:
join bbx = bind bbx id
Here "id" is the identity function - i.e., a function that takes one
argument, and just returns it unchanged. Recall that bind takes a value
out of a box and passes it to a function. Well in this case, the value
in the box is another box, so if we just /return/ that, we'll have only
one level of boxing.
Usually it's bind that you actually want to /use/, and hence it's more
efficient to define join in terms of bind, rather than the other way
around. (Haskell actually lets you define return and bind without
bothering with map at all. Map can be defined in terms of bind and
return, after all: map f = bind (return . f).)
The really hoopy thing, of course, is that this "box" I keep talking
about usually isn't just a simple box. (If it were, that would give you
the identity monad, which is the most boring monad there is.) Usually
it's something more interesting.
For example, if [x] represents a /list/ of x-values (as it does in
Haskell, by the way), then [[x]] is a list of lists, and join is just
flattening a list of lists into a single list. Alternatively, bind is
mapping your function over every element of the list, and then
flattening the resulting list of lists into a single list. (You will
sometimes hear Haskell's bind operator is being "concatMap". "concat" is
a standard library function that does what join does above; "concatMap"
does the same as calling map and then concat.)
Sometimes, however, Haskellers do crazy things, like where your "box
with an x in it" is actually a /function/ which takes half a dozen
arguments and then /returns/ an x. For example, if [x] means "a function
that takes a dictionary and then returns an x", then... Well, we end up
with /a lot/ of different functions flying around, which can sound a bit
confusing. But here it is:
- return(x) just generates a new function that accepts a dictionary,
ignores it, and always returns x anyway.
- map(f,g) is easy enough. Return a function that takes a dictionary,
calls g with that dictionary, and then applies f to the result.
- join(f) is taking a function that returns a function that returns an
x. At this point we don't /have/ a dictionary, so we have nothing to
actually /call/ f with as an argument. But we want to make a function
that takes a dictionary and returns an x. So we write a function that
takes a dictionary argument, calls f with it, and then calls the result
of f again with the same argument.
- Given that we have join() and map(), it's clear that bind() should be
implementable. But can we do it more directly? In fact, all bind(f,g)
does is return a function that takes a dictionary, calls f with that
argument, and then passes the result to g. Quite easy, really.
As a result of all this jiggery-pokery, you can write simple-looking
code, but it invisibly has access to this dictionary that we keep
passing around the place. For that to actually be useful, you need a way
to /fetch/ the dictionary. You go that by writing a function like
get_dictionary :: [dictionary]
Notice that this doesn't appear to be a /function/ at all; it takes no
arguments, after all. But it appears to be a "dictionary in a box" - and
as we just discussed, in this instance our "box" is really "a function
that takes a dictionary and returns something". It should be obvious how
you would write "a function that takes a dictionary and returns a
dictionary".
So this complex arrangement of stuff allows every piece of code that
runs inside this specific monad to have [read-only] access to a
dictionary object. (Obviously it's not hard to change it to be some
other sort of object instead.) This is the so-called "reader monad".
It's all fascinating stuff... but rather mind-bending in places. ;-)
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |