Hi Pascal,


for the 2., yes, the first member of the tuple is the list index in the list-of-lists (i.e for [[1], [2,3], [4,5,6]], the 0th is [1], and 2nd is [4,5,6]).

The other questions in order:
* Yes the sublists themselves have ascending order elements in themselves (you can just 'map sort' if otherwise).
* I think the computation is non-blocking, even if the sublists themselves are infinite. The conditions for non-blocking'ness are that (1) the sublists are in ascending oreder, and (2) the outer list is finite. I think these are enough.
* The list-of-lists (=outer list) is not sorted. I presume you mean by its sub-lists' heads?

The main idea (which you probably get, but to spell it out :) ) is that in previously we had Left for index 0 and Right for index 1, but now we use tuples as it fits better than using nested Either's.


And on the typing of 'sorts ls rs =  ls ++ rs' -- yes, its about types. There was a simila remark some moths ago in the lines of if say you have a function:

f :: Either Int Integer -> Either Int String

then why doesn't this work:

f (Right x) = Right (show x)
f left = left

The trouble is the second definition where 'left' on both sides of the definition is a Left with an Int in it, but the types the lhs and rhs are different. The solution is to spell out both the input and output Left's:

f (Left i) = Left i

The same would go for the lists -- if you expect both of them to be empty, then 'sorts ls rs =  []' would work.


Happy hacking,




On Sun, Dec 14, 2014 at 11:52 PM, Pascal Knodel <pascal.knodel@mail.com> wrote:
Hi Carl,

--------------------------------------- snip ---------------------------------------
module BeginnerStreams where

-- 1. First try:

-- Contract:   Input lists are sorted.
--
-- Notes:
--
--   (!) Duplicate elements are allowed.
--   (!) Sort `Left` before `Right`.


sorts :: Ord a => [a] -> [a] -> [Either a a]
sorts (l : ls) (r : rs)

 |  l <= r     = Left l :           sorts      ls  (r : rs)

 |  otherwise  =          Right r : sorts (l : ls)      rs
 -- l >  r

sorts      []  (r : rs) =  Right r : sorts' Right rs
sorts (l : ls)      []  =  Left  l : sorts' Left  ls
sorts      []       []  =  []

sorts' e (i : is) =  e i : sorts' e is
sorts' _      []  =  []


-- The difficulty for me was: "Either".
-- I forgot about it while defining and
-- did wrong in defining the empty list
-- cases in my first definition:
--
--    sorts ls rs =  ls ++ rs
--
-- That isn't possible without constructor application,
-- because of the output type "[Either a a]". Is it?
--
-- Wish there would be GHCi in the exam.

-- Where else did I fail and didn't notice it?
-- What higher order functions would you use to define "sorts"?


-- 2. First try:

-- I'm not sure, what do you mean by 'value itself'?
-- Why is the second tuple (2,1)? Ah, I see, is it sth. like:
--
--  [1,3] is index 0 and becomes (0,1), (03)
--  [2,3]          1             (1,2), (1,3)
--  ...
--
-- And those sorted in ascending order by the sum of the components?
-- Is it possible to stream this computation without blocking?
-- Is the list-of-lists sorted?
--------------------------------------- snip ---------------------------------------

The exercises from old exams that I have solved are at:
https://github.com/pascal-knodel/Programming-Paradigms-KIT-2014-2015/tree/master/3



Pascal


_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners


--
Carl Eyeinsky