 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Yah. :-) I'll have to ponder this s'more.
Understanding *all* of the underlying theory takes a bit of getting used
to. (Wasn't it some physacist who said "you never truly understand new
theories, you just get used to them"?) However, *using* it is pretty simple.
do
foo
bar
baz
It does those things in the order given. If you assign a result to a
variable, that result stays the same thereafter. And you can do
do
foo
let x = print "hello"
bar
x
which will print "hello" immediately after performing "bar". Nothing
hard here. ;-)
Now, the *list* monad... that's another matter! ;-) Not to mention the
Continuation monad. Even the documentation states that "incautious use
of this monad will result in completely unmaintainable code". But then,
that monad is basically for implementing new flow control constructs -
need I say more?
<long theoretic lecture on monads>
Consider the Maybe monad. It's useful for functions that might fail. For
example,
solve :: Double -> Double -> Maybe Double
solve a b = if a == 0 then Nothing else Just ((0 - b)/a)
Now, what if you wanted to perform *several* operations in sequence,
each of which might fail? This is what the monadic structure of Maybe
implements:
foo j k = do
x <- solve j k
z <- lookup x table
...etc...
This is equivilent to
foo j k =
solve j k >>= \x -> lookup x table >>= ...
So you see that ">>=" takes a Maybe and a function that returns a Maybe,
and... well, let me just write the code, it's faster:
(Just x) >>= f = f x
(Nothing) >>= f = Nothing
So when you do "solve j k >>= f", if solve returns Nothing, just skip f
completely and return Nothing directly. Otherwise, take whatever data
came from solve, fish it out of the Maybe value, and feed it to f.
In other words, we can now have a chain of actions where a single
failure triggers an escape from the whole sequence - but doesn't clutter
up the logic of the program on paper.
Now we can do exactly the same thing with lists. If you think about it,
a Maybe stores either 0 or 1 results. Well, a list can store 0 or 1 or 2
or 3 or...
xs >>= f = concat (map f xs)
As should be clear, if xs is the empty list, f is never run at all, and
you just get an empty list as the result. This is like the Maybe case.
Assuming xs is a nonempty list, run f for every element in xs and merge
the results.
It gets slightly confusing when you start using do-notation, but it's
quite powerful:
factors k = do
x <- [1..10]
y <- [1..10]
if x * y == k then [(x,y)] else []
This is a very stupid algorithm for finding all factors of k, but it
illustrates how you can use the monadic structure of lists. Saying "x <-
xs" basically means "x takes on all values in xs". Having two such lines
causes the second one to cycle faster than the first one, yielding a
Cartesian product.
Now notice that
do
x <- xs
y <- ys
f x y
is rather like the list comprehension syntax
[ f x y | x <- xs, y <- ys ]
In fact, not "rather like", but "mathematically equivilent". Apparently
in older versions of Haskell, comprehensions were permitted for
*arbitrary monads*! But it was eventually decided that this is just "too
insane" and so they removed it. Heh!
Notice that if you write
factors k = do
x <- [1..]
y <- [1..]
if x * y == k then [(x,y)] else []
you get an infinite loop. It tries all possibilities for y before moving
on to the next possibility for x. To overcome this, you need a custom
monad. My book at home shows you how to implement a "diagonal list"
monad. It looks just like a list, but the [very complicated] monadic
bind tackles combinations in diagonal order. [(1,1), (2,1), (1,2),
(3,1), (2,2), (1,3), (4,1), (3,2), (2,3), etc.] The bind function given
is possibly the most terrifying snippet of Haskell I have ever seen in
my life...
</long theoretic lecture on monads>
PS. If you've got a moment, there's a Tcl implementation of my logic
solver over in the povray.off-topic.haskell. I'd be interested to know
if you can make it any less... butt-ugly, for want of a better word!
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> It does those things in the order given. If you assign a result to a
> variable, that result stays the same thereafter.
OK. Same as Erlang. :-)
> And you can do
>
> do
> foo
> let x = print "hello"
> bar
> x
>
> which will print "hello" immediately after performing "bar". Nothing
> hard here. ;-)
Same as Erlang, except you'd have to make it explicitly a fun (aka lambda).
> Consider the Maybe monad. It's useful for functions that might fail. For
> example,
>
> solve :: Double -> Double -> Maybe Double
> solve a b = if a == 0 then Nothing else Just ((0 - b)/a)
solve(A,B) when A == 0 -> nothing;
solve(A,B) -> ((0-B)/A).
(Note that "nothing" here is just an "atom", i.e., an interned string, a
LISP "symbol", a Smalltalk "symbol", etc. It's not a special value or
type. Just something you can match on later.)
> So you see that ">>=" takes a Maybe and a function that returns a Maybe,
> and... well, let me just write the code, it's faster:
>
> (Just x) >>= f = f x
> (Nothing) >>= f = Nothing
>
> So when you do "solve j k >>= f", if solve returns Nothing, just skip f
> completely and return Nothing directly. Otherwise, take whatever data
> came from solve, fish it out of the Maybe value, and feed it to f.
do_maybe(Fun, X) when X == nothing -> nothing;
do_maybe(Fun, X) -> Fun(X).
Probably not equivalent in a deeper sense.
But you're giving me some ideas for some higher-order functions I
probably need. I still miss "while" loops, but I've been trying to
figure out how to make while() into a function that takes two lambdas. :-)
> In other words, we can now have a chain of actions where a single
> failure triggers an escape from the whole sequence - but doesn't clutter
> up the logic of the program on paper.
Yep.
> Now we can do exactly the same thing with lists. If you think about it,
> a Maybe stores either 0 or 1 results. Well, a list can store 0 or 1 or 2
> or 3 or...
>
> xs >>= f = concat (map f xs)
>
> As should be clear, if xs is the empty list, f is never run at all, and
> you just get an empty list as the result. This is like the Maybe case.
> Assuming xs is a nonempty list, run f for every element in xs and merge
> the results.
>
> It gets slightly confusing when you start using do-notation, but it's
> quite powerful:
>
> factors k = do
> x <- [1..10]
> y <- [1..10]
> if x * y == k then [(x,y)] else []
In Erlang:
factors(K) ->
Seq = lists:seq(1,K),
[ X*Y || X <- Seq, Y <- Seq, X * Y == K ].
Thanks for the explanation. I'm still not 100% sure what the "value" in
the monad returned by getclock looks like, tho. I know it's supposed to
be opaque, but what in theory is in there, could you say?
> PS. If you've got a moment, there's a Tcl implementation of my logic
> solver over in the povray.off-topic.haskell. I'd be interested to know
> if you can make it any less... butt-ugly, for want of a better word!
Wow. You have your own newsgroup. :-)
I'll take a look.
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Consider the Maybe monad. It's useful for functions that might fail.
>> For example,
>>
>> solve :: Double -> Double -> Maybe Double
>> solve a b = if a == 0 then Nothing else Just ((0 - b)/a)
>
>
> solve(A,B) when A == 0 -> nothing;
> solve(A,B) -> ((0-B)/A).
>
> (Note that "nothing" here is just an "atom", i.e., an interned string, a
> LISP "symbol", a Smalltalk "symbol", etc. It's not a special value or
> type. Just something you can match on later.)
Heh. I remember using symbols in Smalltalk. Just for the love of God,
don't try to mutate them...!
>> (Just x) >>= f = f x
>> (Nothing) >>= f = Nothing
>
> do_maybe(Fun, X) when X == nothing -> nothing;
> do_maybe(Fun, X) -> Fun(X).
>
> Probably not equivalent in a deeper sense.
No, that's more or less exactly it. Oh, except that "f" is type
constrained to *also* return a Maybe value. (But not necessarily
containing the same type of data.)
> But you're giving me some ideas for some higher-order functions I
> probably need. I still miss "while" loops, but I've been trying to
> figure out how to make while() into a function that takes two lambdas. :-)
Well now, doesn't that rather depend on what this loop is supposed to
*do*? ;-) In Haskell, we have several different while loops, all for
different jobs.
There's takeWhile, dropWhile and span which chop up segments of lists.
There's "unfoldr" which builds lists. There's "until", which repeats a
computation until a condition holds, and returns the final result. And
so on...
>> factors k = do
>> x <- [1..10]
>> y <- [1..10]
>> if x * y == k then [(x,y)] else []
>
> In Erlang:
> factors(K) ->
> Seq = lists:seq(1,K),
> [ X*Y || X <- Seq, Y <- Seq, X * Y == K ].
Like I said, Haskell also possesses list comprehensions, and they are
intimately related to monadic expressions. In Haskell, one could write
[ x*y | x <- seq, y <- seq, x * y == k ]
Interestingly, Haskell possesses a "guard" function:
guard (x*y == k)
return (x,y)
If the condition fails, guard aborts the rest. Otherwise it continues.
Similarly "when" runs or doesn't run just one part of a computation.
I should perhaps also mention "return" and "fail" somewhere. All monads
have a "return" method that inserts a single element into the monad:
return 5 >>= print
is the same as just "print 5". The "fail" method takes a text message
and aborts the computation. For Maybe or lists, the message is ignored,
but for the IO monad it throws an exception. There are monads that allow
you to actually *use* the description for something useful. It's
basically so that pattern match failures inside a monad trigger the
monad's error-handling abilities rather than throw an exception...
> Thanks for the explanation. I'm still not 100% sure what the "value" in
> the monad returned by getclock looks like, tho. I know it's supposed to
> be opaque, but what in theory is in there, could you say?
Theoretically, you might have something like
data IO x =
CMD_GET_CHAR Handle |
CMD_PUT_CHAR Handle |
CMD_TEST_EOF Handle |
...
CMD_GET_CLOCK_TIME |
...
But in reality, I believe GHC actually implements it as a structure
holding a raw pointer to a C function that actually does the work. Note
that it's 100% compiler-specific how IO is actually implemented though.
It's completely outside the language spec... ;-)
So, when you hold an "IO Int", you're probably just holding a pointer to
a C function which, when executed, is going to return an integer.
> Wow. You have your own newsgroup. :-)
Where *have* you been dear boy? ;-)
> I'll take a look.
TY.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>> figure out how to make while() into a function that takes two lambdas.
>
> There's takeWhile, dropWhile and span which chop up segments of lists.
> There's "unfoldr" which builds lists. There's "until", which repeats a
> computation until a condition holds, and returns the final result. And
> so on...
Erlang has all that stuff. They aren't "while" loops, tho, they're "for"
loops. No way to stop foldr() early, no way to have it get its stuff by
(say) reading lines from a file instead of a list, etc.
No way to say "while you haven't gotten to a directory entry that starts
with the letter 'T' in /tmp, ...."
> Interestingly, Haskell possesses a "guard" function:
>
> guard (x*y == k)
> return (x,y)
>
> If the condition fails, guard aborts the rest. Otherwise it continues.
That's what the "when" stuff above is - guards.
And a case statement and an if statement both use guards, as does the
message receiving. The languages do seem very close to each other in
capability, from my naive view.
> I should perhaps also mention "return" and "fail" somewhere. All monads
> have a "return" method that inserts a single element into the monad:
>
> return 5 >>= print
Odd name. Not sure what that means. :-)
> is the same as just "print 5". The "fail" method takes a text message
> and aborts the computation. For Maybe or lists, the message is ignored,
> but for the IO monad it throws an exception.
And Erlang crashes the process out, which sends "I crashed" messages to
anyone "linked" to that process, which in turn either crashes them out
or just queues a message saying they crashed.
> Theoretically, you might have something like
>
> data IO x =
> CMD_GET_CHAR Handle |
> CMD_PUT_CHAR Handle |
> CMD_TEST_EOF Handle |
> ...
> CMD_GET_CLOCK_TIME |
> ...
Hrm. OK.
>> Wow. You have your own newsgroup. :-)
> Where *have* you been dear boy? ;-)
Well, I remember it being created as a joke, but I never subscribed. :-)
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Orchid XP v8 wrote:
>>> figure out how to make while() into a function that takes two lambdas.
>>
>> There's takeWhile, dropWhile and span which chop up segments of lists.
>> There's "unfoldr" which builds lists. There's "until", which repeats a
>> computation until a condition holds, and returns the final result. And
>> so on...
>
> Erlang has all that stuff. They aren't "while" loops, tho, they're "for"
> loops. No way to stop foldr() early, no way to have it get its stuff by
> (say) reading lines from a file instead of a list, etc.
foldr is a for-loop, but unfoldr *is* a while-loop, as are the others I
quoted.
> No way to say "while you haven't gotten to a directory entry that starts
> with the letter 'T' in /tmp, ...."
do
fs0 <- getDirectoryContents "/tmp"
let fs1 = sort fs0
let fs2 = takeWhile (\f -> head f /= 'T') fs1
mapM (stuff) fs2
>> return 5 >>= print
>
> Odd name. Not sure what that means. :-)
Definitely an odd choice of name! "insert" or something would at least
make more sense. (That's what it does after all - insert a pure value
into a monadic wrapper...)
>> The "fail" method takes a text message
>> and aborts the computation. For Maybe or lists, the message is
>> ignored, but for the IO monad it throws an exception.
>
> And Erlang crashes the process out, which sends "I crashed" messages to
> anyone "linked" to that process, which in turn either crashes them out
> or just queues a message saying they crashed.
Haskell has a function called "error" which takes a message and then
throws an exception containing that message. Unless exceptions are
caught somewhere [which can only happen in the IO monad], the default
behaviour is for the program to exit and write a message to stdout.
"fail" is different to "error" in that it is specific to a particular
monad. So for the IO monad, fail = error. But for Maybe, fail just
returns Nothing. And for some other user-defined monad, it could do
something else instead.
factors k = do
x <- [1..10]
y <- [1..10]
if x*y == k then return (x,y) else fail "not a factor"
That does the same as the other example, while being [debatably] clearer.
>>> Wow. You have your own newsgroup. :-)
>> Where *have* you been dear boy? ;-)
>
> Well, I remember it being created as a joke, but I never subscribed. :-)
Better yet: As far as anybody knows, messages never expire! >:-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> foldr is a for-loop, but unfoldr *is* a while-loop, as are the others I
> quoted.
I see the confusion. Erlang isn't lazy.
> Better yet: As far as anybody knows, messages never expire! >:-)
Immortally famous!
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> There's takeWhile, dropWhile and span which chop up segments of lists.
> There's "unfoldr" which builds lists. There's "until", which repeats a
> computation until a condition holds, and returns the final result. And
> so on...
I think the "until" is what I was after, but the Erlang syntax for
curried functions is just klunky enough to still make it annoying.
Still, better than a global name for every while loop. :-)
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> I think the "until" is what I was after, but the Erlang syntax for
> curried functions is just klunky enough to still make it annoying.
Ah. Examining unfoldr, I see I was making it too complicated. I was
trying to figure out how to make "while" (or "until") take two lambdas,
one for the condition, one for the "body" of the loop. Much easier to
just have the one function return whether to keep iterating.
Now I can easily say things like "keep prompting and reading a line
until the user actually types an integer."
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> foldr is a for-loop, but unfoldr *is* a while-loop, as are the others
>> I quoted.
>
> I see the confusion. Erlang isn't lazy.
Laziness for the win! (Or for the user-defined control structures,
anyway...) :-D
>> Better yet: As far as anybody knows, messages never expire! >:-)
>
> Immortally famous!
Hell yeah!
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> I think the "until" is what I was after, but the Erlang syntax for
>> curried functions is just klunky enough to still make it annoying.
>
> Ah. Examining unfoldr, I see I was making it too complicated. I was
> trying to figure out how to make "while" (or "until") take two lambdas,
> one for the condition, one for the "body" of the loop. Much easier to
> just have the one function return whether to keep iterating.
>
> Now I can easily say things like "keep prompting and reading a line
> until the user actually types an integer."
Yes indeed. You have found enlightenment...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
