Implementing the map function using only foldRight, foldLeft and unfold in Scala

3
votes

I have to implement the Map function using only the foldRight, foldLeft and unfold. This means that I have to loop through every element in the list and apply a function f to it.

I have declared my own list as follow:

abstract class IntList
case class Nil() extends IntList
case class Cons(h: Int, t: IntList) extends IntList

And I've implemented the foldRight, foldLeft and unfold functions.

and the implementation of the new map function:

def map(ls: IntList, f: Int => Int): IntList = // ??

I've been thinking for a while now, but I don't have a clue where to begin. I may not use recursion in the map function. I'm pretty sure that I have to combine the power of fold and unfold together. Unfold returns a IntList, which is the return type of map. But I'm not sure what I have to give with this function.

Anyone has a clue? :)

2
scalamapfunctional-programming
Hint: You only need either foldLeft or foldRight or unfold. The simplest solution is with foldRight. - Andreas Rossberg
This is a pretty standard task. If you don't have any idea of how to start, google it. - Marcin
I've alreayd googled for a while, but I can't find a similar topic on this problem. I know it's a standard task and it shouldn't be hard, but I just need a starting point. - Devos50
@AndreasRossberg How do you implement map using unfold? - ziggystar

2 Answers

3
votes

Match the types, fill in the arguments to match.

For instance, if you are going to use foldRight, then B must be IntList, because that's the type returned by map. Now fill in the arguments to foldRight with whatever values you have that match the types.

1
votes

[In reply to previous comments.]

I don't know which exact variant of unfold you are given. Assuming it's something like this (in Ocaml, sorry, don't have Scala installed right now):

(* unfold : ('a -> ('b * 'a) option) -> 'a -> 'b list *)

let rec unfold f x =
  match f x with
  | None -> []
  | Some (y, x') -> y :: unfold f x'

Then a solution for map is the following:

let map f = unfold (function [] -> None | x::xs -> Some (f x, xs))

Hope that helps.