CODEWITHSUNDEEP
functionfunctional-programmingocaml
Ilya
Ilya

Reputation: 59

How to make function that operates on lazy lists (aka "Streams")?

I have to make function, that takes two lazy lists and operator (like +, -, *, /) and return one one lazy list after operation. For example, [1;2;3], [2;3;4;5] +, will return [3;5;7;5]. Lazy list introduced like regular because it more readable.

I have idea how it can be, but I have an error after the function() ->. It says This expression has type int lazyList * int lazyList * char -> int lazyList but an expression was expected of type int lazyList.

type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);;

let rec ldzialanie listA listB operator = function
| LCons(xA, xfA), LCons(xB, xfB), '+' -> LCons(xA + xB, function() -> ldzialanie xfA xfB '+')
| LCons(xA, xfA), LCons(xB, xfB), '-' -> LCons(xA - xB, function() -> ldzialanie xfA xfB '-')
| LCons(xA, xfA), LCons(xB, xfB), '/' -> LCons(xA / xB, function() -> ldzialanie xfA xfB '/')
| LCons(xA, xfA), LCons(xB, xfB), '*' -> LCons(xA * xB, function() -> ldzialanie xfA xfB '*')
| LNil, LNil, _ -> LNil
| LNil, LCons(x, xf), _ -> LCons(x, function() -> xf())
| LCons(x, xf), LNil, _ -> LCons(x, function() -> xf())
| LCons(_), LCons(_), _ -> failwith "Not existible operator"
;;

Upvotes: 0

Views: 64

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

This

let rec ldzialanie listA listB operator = function
| LCons(xA, xfA), LCons(xB, xfB), '+' ->

says that evaluating ldzialanie x y z produces a function that takes a triple as argument.
That's not what you want - you want ldzialanie x y z to produce a 'a lazyList.

You want to match on the arguments instead.
You also need to force the tails of your lazy lists when recursing - the recursion needs a 'a lazyList, not a unit -> 'a lazyList.
As a third point, function () -> xf() is equivalent to xf.

let rec ldzialanie listA listB operator = match listA, listB, operator with
    LCons(xA, xfA), LCons(xB, xfB), '+' -> LCons(xA + xB, function() -> ldzialanie (xfA()) (xfB()) '+')
  | LCons(xA, xfA), LCons(xB, xfB), '-' -> LCons(xA - xB, function() -> ldzialanie (xfA()) (xfB()) '-')
  | LCons(xA, xfA), LCons(xB, xfB), '/' -> LCons(xA / xB, function() -> ldzialanie (xfA()) (xfB()) '/')
  | LCons(xA, xfA), LCons(xB, xfB), '*' -> LCons(xA * xB, function() -> ldzialanie (xfA()) (xfB()) '*')
  | LNil, LNil, _ -> LNil
  | LNil, LCons(x, xf), _ -> LCons(x, xf)
  | LCons(x, xf), LNil, _ -> LCons(x, xf)
  | LCons(_), LCons(_), _ -> failwith "Not existible operator"
;;

Let's shorten this a bit.

If you look at the "nil cases", the result when one argument is LNil is the other argument.

let rec ldzialanie listA listB operator = match listA, listB, operator with
    LCons(xA, xfA), LCons(xB, xfB), '+' -> LCons(xA + xB, function() -> ldzialanie (xfA()) (xfB()) '+')
  | LCons(xA, xfA), LCons(xB, xfB), '-' -> LCons(xA - xB, function() -> ldzialanie (xfA()) (xfB()) '-')
  | LCons(xA, xfA), LCons(xB, xfB), '/' -> LCons(xA / xB, function() -> ldzialanie (xfA()) (xfB()) '/')
  | LCons(xA, xfA), LCons(xB, xfB), '*' -> LCons(xA * xB, function() -> ldzialanie (xfA()) (xfB()) '*')
  | LNil, r, _ -> r
  | l, LNil, _ -> l
  | LCons(_), LCons(_), _ -> failwith "Not existible operator"
;;

There's still a lot of duplication in the "non-nil" cases, and it's not completely obvious that the recursion is correct.
If you convert the operator character to a function first, you can condense those to just one case.

I would also let the operator argument go first so you can define for instance let add_lists = ldzialanie (+).

Something like this:

let to_function x = match x with
    '+' -> ( + )
  | '*' -> ( * )
  | '/' -> ( / )
  | '-' -> ( - )
  | _ -> failwith "Non-existent operator";;

let rec ldzialanie_helper op listA listB = match listA, listB with
    LCons(xA, xfA), LCons(xB, xfB) -> LCons(op xA xB, function() -> ldzialanie_helper op (xfA()) (xfB()))
  | LNil, r  -> r
  | l, LNil  -> l;;

let ldzialanie op = ldzialanie_helper (to_function op);;

Upvotes: 1

Jorge Adriano Branco Aires
Jorge Adriano Branco Aires

Reputation: 2300

First of all, there's a some confusion here

let rec ldzialanie listA listB operator = function
    | LCons(xA, xfA), LCons(xB, xfB)

You're saying ldzialanie applied to the arguments listA, listB and operator returns a function. And that function you return takes triple, on which you pattern match.

Rather you should be using match to pattern match on the arguments of ldzialanie, 

let rec ldzialanie listA listB operator = match listA, listB, operator with
    LCons(xA, xfA), LCons(xB, xfB), '+' ->
  | LCons(xA, xfA), LCons(xB, xfB), '-' ->

Or if you prefer to define ldzialanie using function you have to keep in mind that the function is ldzialanie and not ldzialanie listA listB operator. 

let rec ldzialanie2 = function 
     LCons(xA, xfA), LCons(xB, xfB), '+' ->
   | LCons(xA, xfA), LCons(xB, xfB), '-' ->

Also note both versions have different types since the latter takes a triple as an argument. 

ldzialanie  : int lazyList -> int lazyList -> char -> int lazyList 
ldzialanie2 : int lazyList * int lazyList * char -> int lazyList

You need to keep that in mind when making the recursive call.

Regarding how you calculate the result, you should be aware that given LCons(xA, xfA) the type of xfA is not 'a lazyList but unit -> 'a lazyList. So you can't pass xfA as an argument where you need a 'a lazyList.

Upvotes: 0

Related Questions