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: Re: How to delete a range from AVL tree. (jean verdier)
2. Re: Re: How to delete a range from AVL tree.
(Alexander.Vladislav.Popov )
3. Re: randomize the order of a list (Heinrich Apfelmus)
4. Re: Re: [Haskell-cafe] try, seq, and IO (Jeroen van Maanen)
5. Re: Re: [Haskell-cafe] try, seq, and IO (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Fri, 17 Sep 2010 10:12:53 +0200
From: jean verdier <[email protected]>
Subject: Re: [Haskell-beginners] Re: How to delete a range from AVL
tree.
To: Stephen Tetley <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="UTF-8"
I think that your compare function has the result inverted, you could
try:
between a b x
| x < a = GT
| x > b = LT
| otherwise = EQ
I think that the tree is correct.
On Fri, 2010-09-17 at 08:41 +0100, Stephen Tetley wrote:
> Hello Alexander
>
> I suspect mydelete' isn't working because it needs a "sorted" tree -
> either the initial tree you are supplying isn't sorted or it becomes
> unsorted after one delete step.
>
> I don't know the AVL library at all (I only installed it now to look
> at your problem) so I can't say from looking at the constructors
> whether the problem tree is malformed, the problem tree being:
>
> > P (Z E 1 E) 3 E
>
> Potentially very few people use the Avl module which is why you
> haven't had a reply yet. You could try posting to the Cafe instead if
> you don't get a better answer.
>
> Best wishes
>
> Stephen
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 2
Date: Fri, 17 Sep 2010 14:25:44 +0600
From: "Alexander.Vladislav.Popov "
<[email protected]>
Subject: Re: [Haskell-beginners] Re: How to delete a range from AVL
tree.
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="utf-8"
Thank you very much, Stephen and Jean!
I guess I missed something in my tests.
You definition gives me valid results.
How I can missed it!
Thank you very much again!
2010/9/17 jean verdier <[email protected]>
> I think that your compare function has the result inverted, you could
> try:
>
> between a b x
> | x < a = GT
> | x > b = LT
> | otherwise = EQ
>
> I think that the tree is correct.
>
>
> On Fri, 2010-09-17 at 08:41 +0100, Stephen Tetley wrote:
> > Hello Alexander
> >
> > I suspect mydelete' isn't working because it needs a "sorted" tree -
> > either the initial tree you are supplying isn't sorted or it becomes
> > unsorted after one delete step.
> >
> > I don't know the AVL library at all (I only installed it now to look
> > at your problem) so I can't say from looking at the constructors
> > whether the problem tree is malformed, the problem tree being:
> >
> > > P (Z E 1 E) 3 E
> >
> > Potentially very few people use the Avl module which is why you
> > haven't had a reply yet. You could try posting to the Cafe instead if
> > you don't get a better answer.
> >
> > Best wishes
> >
> > Stephen
> > _______________________________________________
> > Beginners mailing list
> > [email protected]
> > http://www.haskell.org/mailman/listinfo/beginners
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100917/f25ce943/attachment-0001.html
------------------------------
Message: 3
Date: Fri, 17 Sep 2010 10:38:23 +0200
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: randomize the order of a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
John Dorsey wrote:
> Heinrich Apfelmus wrote:
>
>> Embarrassingly, the analysis in my previous message is wrong, though.
>> Here an actually correct assessment of the algorithm. Or rather, of the
>> two algorithms; the results are different depending on whether you use a
>> pivot *element* or just a pivot *position*. It will turn out that the
>> former is not uniform, while, to my surprise, the latter is uniform!
>
> And this was my point. I never considered a pivot *element*, which you
> correctly point out wouldn't work so well. I was referring to a pivot taken
> from a randomly chosen *position*. On re-reading Gabriel Scherer's original
> musing:
>
>>>>> Thanks for the link apfelmus, it's fairly interesting. The key to
>>>>> making it work is the weighting of lists during merging based on their
>>>>> lengths. I wonder if other sort algorithm can be adapted in such a
>>>>> way, while preserving uniformity. Quicksort for example : is it enough
>>>>> to choose the result position of the pivot randomly, and then placing
>>>>> elements on either side with a probability of 1/2 ?
>
> I may have misunderstood his original intent, as he refers to a random
> "result position" for a pivot (chosen how?). But if that's changed to
> choosing the pivot from a random position, then it works out nicely. I
> think you agree with this later in your email.
>
> And finally, re-reading your earlier comment:
>
>>>> First, you can skip choosing the pivot position because it is already
>>>> entailed by the choices of elements left and right to it.
>
> I think I understand now what you were referring to... (redundantly)
> choosing the destination for a pivot chosen by some other unspecified means.
It probably helps to write down some code for the different
possibilities. :)
* Pivot element, position chosen by a dice roll. This is closest to
quicksort in spirit.
quickshuffle (x:xs) = do
k <- uniform [0..length xs]
(ls,rs) <- partition k xs -- satisfies length ls == k
sls <- quickshuffle ls
srs <- quickshuffle rs
return (ls ++ [x] ++ rs)
* Pivot element, position fixed. This is Gabriel's solution.
quickshuffle (x:xs) = do
let k = length xs `div` 2
(ls,rs) <- partition k xs -- satisfies length ls == k
sls <- quickshuffle ls
srs <- quickshuffle rs
return (ls ++ [x] ++ rs)
* Pivot element, position entailed by the random partition.
quickshuffle (x:xs) = do
(ls,rs) <- partition xs
sls <- quickshuffle ls
srs <- quickshuffle rs
return (ls ++ [x] ++ rs)
* Pivot position, chosen by a dice roll. The arguments to the recursive
calls to quickshuffle are no longer guaranteed to be smaller; the
algorithm might run for an arbitrarily long time.
quickshuffle xs = do
k <- uniform [0..length xs]
(ls,rs) <- partition k xs -- satisfies length ls == k
sls <- quickshuffle ls
srs <- quickshuffle rs
return (ls ++ rs)
* Pivot position, entailed by the random partition. This is the only
algorithm where picking elements to the left or the right with
probability 1/2 gives a uniform permutation. Same problem with
potentially arbitrarily long running times, though.
quickshuffle xs = do
(ls,rs) <- partition xs
sls <- quickshuffle ls
srs <- quickshuffle rs
return (ls ++ rs)
The partition functions needed to get permutations with uniform
probability are quite different for the different algorithms.
Regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 4
Date: Fri, 17 Sep 2010 13:17:30 +0200
From: Jeroen van Maanen <[email protected]>
Subject: Re: [Haskell-beginners] Re: [Haskell-cafe] try, seq, and IO
To: Dean Herington <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Op 2010-09-17 06:32, Dean Herington schreef:
> At 10:54 AM +0200 9/16/10, Jeroen van Maanen wrote:
>> Op 2010-09-16 08:50, Jeroen van Maanen schreef:
>> [...]
>>
>> Gregs suggestion provided the way out: evaluate. My code now looks like this:
>>
>> do let maybeUpdatedModel = f update startModel
>> theCheckSum = maybe 0 checkSum maybeUpdatedModel
>> logException exception = logger "Exception" [showString
>> label, shows (exception :: SomeException)] >> return Nothing
>> logger "Received update" [showString label, logs update]
>> resultOrException <- try $ evaluate $ seq theCheckSum
>> maybeUpdatedModel
>> maybeNextModel <- either logException return resultOrException
>> logger "Maybe next model" [showString label, logs maybeNextModel]
>> -- ...
>>
>> I still don't understand why evaluating maybeUpdatedModel to WHNF after seq
>> evaluated theCheckSum to WHNF forces the lurking exception to the surface.
>> Or is the phrase 'when the resultant IO action is executed' in the
>> documentation of 'evaluate' significant here?
>
> I still don't follow all your code, but presuming maybeUpdatedModel is of
> non-IO type, I'm guessing it's the evaluation of theCheckSum that causes
> evaluation of maybeUpdatedModel (which raises the exception).
What I don't understand is the difference between:
try $ return $ seq theCheckSum maybeUpdatedModel
or even
try $! return $! seq theCheckSum maybeUpdatedModel
and
try $ evaluate $ seq theCheckSum maybeUpdatedModel
How is it possible that the exception escapes the former two expressions, but
gets caught by the third try?
Cheers, Jeroen
------------------------------
Message: 5
Date: Fri, 17 Sep 2010 15:18:21 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: [Haskell-cafe] try, seq, and IO
To: [email protected]
Cc: Jeroen van Maanen <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Friday 17 September 2010 13:17:30, Jeroen van Maanen wrote:
> What I don't understand is the difference between:
>
> try $ return $ seq theCheckSum maybeUpdatedModel
>
> or even
>
> try $! return $! seq theCheckSum maybeUpdatedModel
>
> and
>
> try $ evaluate $ seq theCheckSum maybeUpdatedModel
>
> How is it possible that the exception escapes the former two
> expressions, but gets caught by the third try?
>
> Cheers, Jeroen
It's quite devilish :)
Well, the first and the third are rather straightforward.
Let's start with the third.
What that does is, evaluate (seq theCheckSum maybeUpdatedModel) to WHNF, if
that throws an exception (of appropriate type, here SomeException), return
(Left exception) else return (Right result). To evaluate `seq theCheckSum
maybeUpdatedModel' to WHNF, theCheckSum has to be evaluated to WHNF (hence
completely, since it's an Integer or something like), which in turn
requires the complete evaluation of maybeUpdatedModel.
The last throws an exception, that gets caught and wrapped in try, as
expected and desired.
The first one is `try (return thunk)' where thunk is "if needed, calculate
`seq theCheckSum maybeUpdatedModel'". The return succeeds immediately, try
wraps it in a Right and returns (Right thunk), as expected but not desired.
The exception is thrown when you demand the evaluation of the thunk, after
try has been left. Too lazy.
Now the second one.
try $! return $! seq t m
=== let z = return $! seq t m in z `seq` try z
=== let z = let v = seq t m in v `seq` return v in z `seq` try z
=== let { v = seq t m; z = v `seq` return v } in z `seq` try z
=== let v = seq t m in (v `seq` return v) `seq` try (return v)
=== ((t `seq` m) `seq` (return (t `seq` m)) `seq` try (return (t `seq` m))
So before try is even called, t has to be evaluated to WHNF, which throws
an exception. Since it's thrown before try has been entered, try can't
catch it. Too strict.
So, first gives an uncaught exception after try has been left, second gives
an uncaught exception before try has been entered.
How do we get the exception to be thrown inside the try?
That's easy. We mustn't allow try to return an exception-throwing thunk, so
we need (return $! seq t m).
But we mustn't cause the exception before try has been entered, so we need
try $ return $! seq theCheckSum maybeUpdatedModel
w00t
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 27, Issue 41
*****************************************
