Seite 1 von 1

Fourth Assignment

Verfasst: 6. Mai 2012 21:02
von Wambolo
Hi,

reagrding test5b [(2, 20), (2, 25), (3, 35), (5, 50), (7, 70)] is the correct computation of (mergeLists (\(k1, v1) (k2, v2) -> k1 < k2) [[(2, 20), (5, 50), (7, 70)], [(2, 25), (3, 35)]])

Why shouldn't [(2,25), (2,20),...] be correct too. Have I overlooked some implicit specifications?

Re: Fourth Assignment

Verfasst: 7. Mai 2012 08:59
von olg
I've come across the same issue. The test either works with <= as the operator of k1,k2 , or with (2,20),(2,25) replaced in the solution.

Re: Fourth Assignment

Verfasst: 7. Mai 2012 11:20
von nt4u
I think the tests assume stability.

Re: Fourth Assignment

Verfasst: 7. Mai 2012 11:49
von olg
In order to provide stability, shouldn't the comparator function be as follows (in order to provide EQ for stability) ?
a -> a -> Ordering
In the current implementation, the function (\(k1, v1) (k2, v2) -> k1 < k2) obviously returns false for (2,20)(2,25) and thus indicates that the pairs should indeed are not sorted. Using Ordering, we can distinguish this special case, and ignore the switch.

Re: Fourth Assignment

Verfasst: 7. Mai 2012 12:04
von DanielSchoepe
olg hat geschrieben:In order to provide stability, shouldn't the comparator function be as follows (in order to provide EQ for stability) ?
a -> a -> Ordering
In the current implementation, the function (\(k1, v1) (k2, v2) -> k1 < k2) obviously returns false for (2,20)(2,25) and thus indicates that the pairs should indeed are not sorted. Using Ordering, we can distinguish this special case, and ignore the switch.
You can already achieve the same result with the given function (assuming that it decides a total ordering) by considering op y x. If that doesn't hold, you know that \(\neg (y < x)\) and thus \(y \ge x\); if it does hold, we have \(y < x\), which should give you enough information to decide how to order x and y (with "<" being the thing op decides, not integer comparison) in a stable manner.

Re: Fourth Assignment

Verfasst: 8. Mai 2012 12:37
von doemel
grml ... hat sich erledigt

Re: Fourth Assignment

Verfasst: 8. Mai 2012 15:54
von sewe
doemel hat geschrieben:grml ... hat sich erledigt
What was the problem with map? (Please don't delete your orignal post; maybe others can learn from your experience.)

Re: Fourth Assignment

Verfasst: 11. Mai 2012 09:56
von sewe