Sort Issue. Haskell.
Tige
i wrote for it.
sort3 :: Int -> Int -> Int -> (Int, Int, Int)
sort3 a b c | a<=b && b<=c = (a,b,c)
| c<=b && b<=a = (c,b,a)
| b<=a && a<=c = (b,a,c)
| c<=a && a<=b = (c,a,b)
| b<=c && c<=a = (b,c,a)
| a<=c && c<=b = (a,c,b)
I am sure that you can tell me a neater way on how to do this. The way i
figured i would go about is, with 3 numbers, you have 6 different choices,
so that's where the code's from.
Now, here's the question that i can't figure out.
What is the minimal number of comparisons needed to implement sort3? Less
than three comparisons will generally not be sufficient, but in fact it is
possible to restrict the implementation to not using more than three
comparisons. Write a second version of sort3 - call it sort3' (i.e., a prime
character added after the previous name of the function) - but this time,
the function is not allowed to use more than three comparisons to compute
the result. Hints: You will have to use a where clause.
Here is a solution that i don't understand.
sort3' :: Int -> Int -> Int -> (Int, Int, Int)
sort3' x y z = (smallest, middle, greatest)
where
(smallOrMiddle, middleOrGreat1) = sort2 x y
(smallest, middleOrGreat2) = sort2 smallOrMiddle z
(middle, greatest ) = sort2 middleOrGreat1
middleOrGreat2
Keep it in mind that i am very new to Haskell. I don't understand what the
course pack writer's done. He's being clever i get that.
In that he's using pattern matching to define variables such as
smallOrMiddle, middleOrGreat1 etc. But, is there a way with which
i can write code with which it would make more sense than that? Can someone
explain a simpler way on doing this to me?
Lars Lundgren
>
> What is the minimal number of comparisons needed to implement sort3?
Isnt it (n-1)*ceil(log2(n-1)) or something? (just guessing) In the case
where n=3 that would mean 3.
> Here is a solution that i don't understand.
>
> sort3' :: Int -> Int -> Int -> (Int, Int, Int)
> sort3' x y z = (smallest, middle, greatest)
> where
> (smallOrMiddle, middleOrGreat1) = sort2 x y
> (smallest, middleOrGreat2) = sort2 smallOrMiddle z
> (middle, greatest ) = sort2 middleOrGreat1
> middleOrGreat2
>
> Keep it in mind that i am very new to Haskell. I don't understand what the
> course pack writer's done. He's being clever i get that.
> In that he's using pattern matching to define variables such as
> smallOrMiddle, middleOrGreat1 etc. But, is there a way with which
> i can write code with which it would make more sense than that? Can someone
> explain a simpler way on doing this to me?
>
The above code is about as simple as it gets. You are probably just unused
to the syntax. sort2 returns a tuple with the two elements in order. I
will try to explain what the code does.
If you compare x and y, then the smallest of them must be smallest of
(x,y,z) or must be the middle element - thus a good name for it would be
smallOrMiddle. In the same way, the greatest of x and y must be the middle
element or the greatest element of (x,y,z) - lets call it middleOrGreat1.
Lets then compare smallOrMiddle with z. The smallest of them must be the
smalest of (x,y,z) so we better call it smallest then. The other element
could possibly be the greatest, or the middle element, so we call it
middleOrGreat2. Finally we compare thw two middleOrGreat elements. The
smallest of them must be the middle element and the greatest of them must
be the greatest element of (x,y,z). Now you have an element called
smallest, an element called middle and an element called greatest. Just
put them together in a 3-tuple and you are finished.
Please explain to me: How could it be any simpler?
/Lars L
George Russell
>
> Okay, so you have three numbers that you need to sort. This is the code that
> i wrote for it.
>
> sort3 :: Int -> Int -> Int -> (Int, Int, Int)
> sort3 a b c | a<=b && b<=c = (a,b,c)
> | c<=b && b<=a = (c,b,a)
> | b<=a && a<=c = (b,a,c)
> | c<=a && a<=b = (c,a,b)
> | b<=c && c<=a = (b,c,a)
> | a<=c && c<=b = (a,c,b)
>
> I am sure that you can tell me a neater way on how to do this. The way i
> figured i would go about is, with 3 numbers, you have 6 different choices,
> so that's where the code's from.
>
> Now, here's the question that i can't figure out.
>
> What is the minimal number of comparisons needed to implement sort3?
is the lowest N with 2^N >= n!. This gives N=3, and an algorithm is not hard
to discover.
Similarly it shouldn't be too hard to show you can sort 4 elements in 5 comparisons.
I leave it as an exercise whether you can sort 5 elements in 7 comparisons . . .
Tige
Write a function bothTrue:: Bool -> Bool -> Bool that returns True if and
only if both its inputs are True.
Lab03> bothTrue True False
False
Lab03> bothTrue True True
True
Lab03> bothTrue False False
False
Lab03> bothTrue False True
False
Lab03> bothTrue (6 < 100) ('a' < 'b')
True
Lab03> bothTrue ("Haskell" == "uncool") (4*5 == 20)
False
Can you do this without using pattern matching or the && function?
bothtrue :: Bool -> Bool -> Bool
bothtrue a b |a/=b = False
|a==False && b==False = False
|a==b = True
So, this is the code i wrote. But, it uses both Pattern matching as well as
the && Function.
I hope it doesn't bother anyone that i am asking so many questions.
Ralph Becket
Tige <r.sunda...@student.unsw.edu.au.removethis> wrote:
>What is the minimal number of comparisons needed to implement sort3?
For quantities ranging over infinite domains the best you can do in
general is O(n.log n) comparisons to sort n items. For three numbers
we get 3.log_2 3 = 4.76.
However, the following three stage sorting network will do the trick
in just three compare-and-swap steps. Each vertical line represents
a compare-and-swap placing the smaller of the two quantities above
the other:
x --+-----+-->
| |
y --+--+--+-->
|
z -----+----->
It's obvious that after the first two compare-and-swaps that z will
hold the largest quantity, leaving a single compare-and-swap to
order x and y.
In Mercury one might implement this as
sort_XYZ(XYZ) = sort_XY(sort_YZ(sort_XY(XYZ)))
sort_XY({X, Y, Z}) = if X =< Y then {X, Y, Z} else {Y, X, Z}.
sort_YZ({X, Y, Z}) = if Y =< Z then {X, Y, Z} else {X, Z, Y}.
This is pretty much what the code that has you confused is doing.
Cheers,
Ralph
--
Ralph....@cl.cam.ac.uk
Nick Chapman
writes
>Similarly it shouldn't be too hard to show you can sort 4 elements in 5
>comparisons.
>I leave it as an exercise whether you can sort 5 elements in 7 comparisons . . .
I remembered playing around with this a few years back, so I dug out
some old code...
The following ML implements sort[2345] with the minimum compares
necessary. If I remember right, the algorithm originates from Knuth.
fun compare (a,b) = a < b
fun sort2 (a,b) =
if compare (a,b) then (a,b) else (b,a)
fun sort3 (a,b,c) =
let val (a,b) = sort2 (a,b)
val (b,c) = sort2 (b,c)
val (a,b) = sort2 (a,b)
in (a,b,c)
end
fun insert1in3 (x,(a,b,c)) =
if compare (x,b)
then let val (x,a) = sort2 (x,a)
in (x,a,b,c)
end
else let val (c,x) = sort2 (c,x)
in (a,b,c,x)
end
fun sort4 (a,b,c,d) =
let val (a,b,c) = sort3 (a,b,c)
in insert1in3 (d,(a,b,c))
end
fun sort5 (a,b,c,d,e) =
let val (a,b) = sort2 (a,b)
val (c,d) = sort2 (c,d)
val (a,b,c,d) = if compare (b,d) then (a,b,c,d)
else (c,d,a,b)
(*
a --> b --> d
c --/
*)
in
if compare (e,b)
then
(*
e --\
a --> b --> d
c --/
*)
let val (a,e) = sort2 (a,e)
val (c,a,e,b) = insert1in3 (c,(a,e,b))
in (c,a,e,b,d)
end
else
(*
/--> e
a --> b --> d
c --/
*)
let val (e,d) = sort2 (e,d)
val (c,a,b,e) = insert1in3 (c,(a,b,e))
in (c,a,b,e,d)
end
end
--
Nick Chapman <n...@truthmachine.demon.co.uk>
Lars Lundgren
>
> bothtrue :: Bool -> Bool -> Bool
> bothtrue a b |a/=b = False
> |a==False && b==False = False
> |a==b = True
>
>
> So, this is the code i wrote. But, it uses both Pattern matching as well as
> the && Function.
I do not see any patternmatching in your implementation. What do you have
against pattern matching? To solve the problem you need to inspect the
values of the arguments. Pattern matching is a convenient way to do that.
bothTrue:: Bool -> Bool -> Bool
implementation1:
bothTrue False x = False
bothTrue True x = x
implementation2:
bothTrue = (&&)
implementation3:
bothTrue a b = not(not a || not b)
/Lars L
Peter Hancock
bothtrue :: Bool -> Bool -> Bool
?? what a strange question.
Peter Hancock
Jón Fairbairn
> In article <9imd0o$nka$1...@tomahawk.unsw.edu.au>,
> Tige <r.sunda...@student.unsw.edu.au.removethis> wrote:
> >What is the minimal number of comparisons needed to implement sort3?
>
> For quantities ranging over infinite domains the best you can do in
> general is O(n.log n) comparisons to sort n items. For three numbers
> we get 3.log_2 3 = 4.76.
Um. logBase 2 (n!), surely?* Stirling isn't too hot for small
numbers. Mind you logBase 2 6 = 2.58..., but I make the mean number of
comparisons necessary 2.66... :-) Oh, ceiling...
(comparing the first pair first,
1 \ ok
2 / \ ok
3 /
2 \/ 1
1 /\ 2 \ ok
3 /
are the two cases that can be done in two comparisons, the remaining
four take three since the second comparison says merely that the last
element is less than the second, not whether it's also less than the
first.)
Jón
* for the original poster: the result comes from thinking about the
size of the decision tree. If you plot out what the programme could
do after each comparison, you get a binary tree. An input with n
elements can be in any of n! permutations, so there must be n!
different possible outcomes of sorting n elements (You could imagine
a programme that did all the comparisons first and then shuffled
them into the right order at the end). The height of a binary tree
with m leaves is ceiling (logBase 2 m)
--
Jón Fairbairn Jon.Fa...@cl.cam.ac.uk
Jón Fairbairn
> bothtrue :: Bool -> Bool -> Bool
> bothtrue a b = not (not a || not b)
>
> ?? what a strange question.
Indeed. Doesn't your answer _use_ pattern matching, since that's how
not &c are implemented? Maybe there's a use/mention distinction
problem here :-)
bothtrue a b = if a then b else a
is just as bad, of course, since if is defined in terms of pattern
matching. So the answer to the original question is "No, I can't
define it without using pattern matching". Sorted.
--
Jón Fairbairn Jon.Fa...@cl.cam.ac.uk
Ralph Becket
>Tige wrote:
>
>Similarly it shouldn't be too hard to show you can sort 4 elements in 5 comparisons.
>I leave it as an exercise whether you can sort 5 elements in 7 comparisons . . .
Ah, a challenge!
From a sorting network perspective (based on binary compare-and-swap
operations) we might apply a merge sort-like approach (that is, divide
the input vector into two sub-vectors, sort those and merge the results.)
Works a treat:
4-element sorting network with 5 comparisons:
w --+--+-------->
| |
x --+--|--+--+-->
| | |
y --+--+--|--+-->
| |
z --+-----+----->
A B C D
A: sort <w,x> and <y,z>
B: w becomes least elt.
C: z becomes greatest elt.
D: fix up <x,y> ordering.
5-element sorting network with 7 *concurrent stages* (9 comparisons):
v --+-----------+----------->
| |
w --+--------+--|--+-----+-->
| | | |
x --+-----+--|--+--+--+--+-->
| | | |
y --+--+--+--|--------+----->
| |
z -----+-----+-------------->
AAAAAAA BBBB CCCCCCC
A: sort <v,w> and <x,y,z> [3 steps]
B: z becomes greatest elt., v becomes least [1 step]
C: sort <w,x,y> [3 steps]
Try as best I can, I can't seem to find a 7 *comparison*
network. Does such a thing exist or is this a cruel joke :)
- Ralph
gr...@cs.wa.edu.au
: Write a function bothTrue:: Bool -> Bool -> Bool that returns True if and
: only if both its inputs are True.
: bothtrue :: Bool -> Bool -> Bool
: bothtrue a b |a/=b = False
: |a==False && b==False = False
: |a==b = True
: So, this is the code i wrote. But, it uses both Pattern matching as well as
: the && Function.
Doesn't seem to use pattern matching to me.
This doesn't use &&, either:
bothtrue a b = not ((not a)||(not b))
But it might be considered cheating since not and || use pattern matching.
Maybe this is better:
bothtrue a b | a==False = False
| b==False = False
| otherwise = True
I imagine that's what the question is after.
: I hope it doesn't bother anyone that i am asking so many questions.
If it bothered us, we wouldn't answer the questions.
It should only bother you if you're reading our answers instead of learning.
Does it bother your course supervisor? (if this is coursework)
-Greg
ol...@pobox.com
iff both arguments are True) in such a way so to avoid function (&&)
and the pattern-matching facilities of Haskell. Note that functions
'not' and (||) are defined in the Prelude with the use of
pattern-matching. The 'if' function may rely on pattern-matching as well.
One solution:
bothtruth1:: Bool -> Bool -> Bool
bothtruth1 a b = (fromEnum a) + (fromEnum b) == 2
fromEnum does not _explicitly_ use the pattern matching (but it may
implicitly do, in the compiler-derived code).
Another solution:
bothtruth':: Bool -> Bool -> Bool
bothtruth' a b = (a,b) == (True,True)
according to the Hugs prelude, a tuple identity comparison function is built
into the compiler.
The following is a "better" solution. It seems to get by without even
implicit pattern matching. It requires Hugs:
primitive ptr_to_int "unsafePtrToInt" :: a -> Int
bothtruth2:: Bool -> Bool -> Bool
bothtruth2 a b = a `seq` b `seq` (ptr_to_int a - ptr_to_int False) +
(ptr_to_int b - ptr_to_int False) ==
2*(ptr_to_int True - ptr_to_int False)
To verify:
bothtruth2 True True -- --> True
bothtruth2 (1==1) True -- --> True
bothtruth2 (1==2) (1==2) -- --> False
bothtruth2 (1==1) (2==2) -- --> True
bothtruth2 (odd 2) (2==2) -- --> False
bothtruth2 (odd 1) ("Haskell" == "Haskell") -- --> False
Tige
> If it bothered us, we wouldn't answer the questions.
> It should only bother you if you're reading our answers instead of
learning.
> Does it bother your course supervisor? (if this is coursework)
>
> -Greg
No, it wouldn't. :)
It's July 14th, and i am doing next semester's work before i start my
classes on the 23rd.
The stuff i am asking you is from Week3, so if i can get a grasp on what's
going on before
i get into the class, then all the better i say.
Thanks.
gr...@cs.wa.edu.au
:> Does it bother your course supervisor? (if this is coursework)
: No, it wouldn't. :)
: It's July 14th, and i am doing next semester's work before i start my
: classes on the 23rd.
: The stuff i am asking you is from Week3, so if i can get a grasp on what's
: going on before
: i get into the class, then all the better i say.
*Sigh* Why can't we all have students like that?
-Greg
Albert Y. C. Lai
> *Sigh* Why can't we all have students like that?
1. Most students take up summer jobs whenever school hasn't started.
Some of them need the salary to survive, which is sad (they may
wish to spend more time on self study but cannot), but some others
are just greedy and shortsighted.
2. Some students argue "I am paying m dollars for this course, so I
expect to be told everything", where m is maybe one-tenth of the
operational cost of the course, with 9m coming from government
funding.
3. Hey, not all instructors make course materials or even the
citations of the textbooks avaiable in advance. Hey, some courses
do not even appoint instructors in advance. Sometimes the notes
for a lecture are prepared just hours before the lecture, and
sometimes hours after.
Jón Fairbairn
> In article <3B4ED975...@tzi.de>, George Russell <g...@tzi.de> wrote:
> >Tige wrote:
> >
> >Similarly it shouldn't be too hard to show you can sort 4 elements
> >in 5 comparisons. I leave it as an exercise whether you can sort 5
> >elements in 7 comparisons . . .
> From a sorting network perspective (based on binary compare-and-swap
> operations) we might apply a merge sort-like approach (that is,
> divide the input vector into two sub-vectors, sort those and merge
> the results.)
[snippage]
> Try as best I can, I can't seem to find a 7 *comparison*
> network. Does such a thing exist or is this a cruel joke :)
I don't think it does exist, but it's not a _cruel_ joke. The joke is
that you can't do it with a fixed network because to do it in the
optimum number requires that you change which comparisons you do
depending on the results of earlier ones.
On the page below is a Haskell programme that has optimal sorts
including for 5. (I believe that the formfeed will give people the
option of not reading it if they want to work it out for
themselves. Apologies if this doesn't work with your newsreader!)
module Optimal_sorts where
permutations [] = [[]]
permutations (a:as) =
concat (map (insertions a) (permutations as))
where insertions a [] = [[a]]
insertions a (b:bs) = (a:b:bs):
map ((:)b) (insertions a bs)
merge [] b = b
merge a [] = a
merge (a:as) (b:bs) | a <= b = a: merge as (b:bs)
| True = b: merge (a:as) bs
sort2 [a, b] | a <= b = [a, b]
| True = [b, a]
sort3 [c, d, e] = merge [c] (sort2 [d, e])
sort4 [a, b, c, d] = merge (sort2 [a, b])
(sort2 [c, d])
sort4a a [b, c, d] = -- b, c, d in order, always takes two comparisons
if a <= c
then if a <= b
then [a, b, c, d]
else [b, a, c, d]
else if a <= d
then [b, c, a, d]
else [b, c, d, a]
sort5 [a, b, c, d, e] = -- +2 comparisons
sort5a (sort2 [a, b]) (sort2 [c, d]) e
sort5a [a, b] [c, d] e = -- [a, b] and [c, d] in order, +1 comparison
if a <= c
then sort5b (a, (b, (c, d))) e
else sort5b (c, (d, (a, b))) e
sort5b (a, (b, (c, d))) e = -- we have a <= (b, c, d) and b <= (c, d)
-- but e not compared
-- +1 or +2 comparisons
if e <= c
then if e <= a
then e: a: merge [b] [c, d] -- merge adds at most 2 comparisons
else a: sort4a b [e, c, d]
else if e <= d
then a: sort4a b [c, e, d]
else a: sort4a b [c, d, e]
--
Jón Fairbairn Jon.Fa...@cl.cam.ac.uk
Jón Fairbairn
<stuff>
> sort5b (a, (b, (c, d))) e = -- we have a <= (b, c, d) and b <= (c, d)
> -- but e not compared
> -- +1 or +2 comparisons
Bother! The comment should read "-- +2 comparisons". I never did
beleive in comments, 'cause the compiler doesn't check them, so they
go wrong when the programme gets changed.
--
Jón Fairbairn Jon.Fa...@cl.cam.ac.uk