Hello, I'm preparing for an exam (university level introductory course). Functional programming in Haskell is part of it. That includes the concept of streams (theoretically infinite list computations). I have difficulties in solving exercises that ask me to define streams for a given problem. Do you know good examples, the difficulty should be maybe a little harder than Fibonacci or intersections, but solvable in about 5 to 10 minutes. If there are examples from the book "Haskell - the craft of functional programming", please don't spoiler, I'm reading it parallel to this conversation. Don't give solutions, just problems (5 to 10 more will do). Examples, other than integer sequences are welcome. Pascal
Hi, Pascal
(and hi, list!)
1. Here is one: define a function that takes two lists, both of which have
elements in growing order (i.e 1,2,3,3,5,9,9,..), and outputs a list with
the type of [Either a a], where a `Left a' would represent an element from
the first list, a `Right a' from the second list. Make it so that the
elements are in order, and also that the lefts preceede the rights.
Example, the inputs of [1,1,3,7,7] and [1,2,3,5,5] would result in [Left 1,
Left 1, Right 1, Right 2, Left 3, Right 3, Right 5, Right 5, Left 7, Left 7]
2. As an extension (not sure if this is too difficult for what you're
looking for): write another function that takes a list-of-lists as input
and outputs the result in tuples, where the first member is the index of
the list (counting from zero), and the second is the value itself.
Example [[1,3],[2,3],[1,3,4]] should result in
[(0,1),(2,1),(1,2),(0,3),(1,3),(2,3),(2,4)]
On Fri, Dec 12, 2014 at 4:14 AM, Pascal Knodel
Hello,
I'm preparing for an exam (university level introductory course). Functional programming in Haskell is part of it. That includes the concept of streams (theoretically infinite list computations).
I have difficulties in solving exercises that ask me to define streams for a given problem. Do you know good examples, the difficulty should be maybe a little harder than Fibonacci or intersections, but solvable in about 5 to 10 minutes. If there are examples from the book "Haskell - the craft of functional programming", please don't spoiler, I'm reading it parallel to this conversation. Don't give solutions, just problems (5 to 10 more will do). Examples, other than integer sequences are welcome.
Pascal _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- Carl Eyeinsky
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/ma... Pascal
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
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
participants (2)
-
Carl Eyeinsky -
Pascal Knodel