Solve this USING F#
Consider the following functions: // lookup: 'a -> string -> (string * 'a) list -> 'a let rec lookup dv (k: string) = function | [] -> dv | (k', v) :: xs -> if k = k' then v else lookup dv k xs 1/ update : string -> 'a -> (string * 'a) list -> (string * 'a) list let rec update (k : string) v = function | [] -> [(k, v)] (k', ) as p :: xs-> if k = k' then (k, v) :: xs else p :: update k v xs (i) Implement a function count : string -> string list -> int such that count x xs is the number of times the string x appears in the list xs. > count "x" ["y","z"];; val it : int = 0 > count "x" ["x","x":"x"];; val it : int = 3 > count "x" ["y":"x","x";"z";"y"; "y") ;; val it : int = 2 (ii) The following function traverses its input list twice: // modify: 'a-> ('a -> 'a) -> string -> (string * 'a) list -> (string * 'a) list let modify d f x xs = update x (f (lookup d x xs)) xs Reimplement modify so that the list is traversed at most once. (iii) Using modify, implement a function ac : (string * int) list -> string list -> (string * int) list that adds the number of times each string appears in the second list. Your function should satisfy lookup Ox (ac dict xs) = lookup 0 x dict + count x xs for all dict, x, xs. > ac [] ["x":"x""y":"x"; "y") ;; val it : (string * int) list = [("x", 3); ("y", 2)] > ac [("x", 2); ("y",3)) ["x";"y";"z"];; val it : (string * int) list = [("x", 3); ("y", 4); ("z", 1)] > ac [("x", 2);("y",3)) ["x";"x";"x"];; val it : (string * int) list = [("x", 5); ("y", 3)] Consider the following functions: // lookup: 'a -> string -> (string * 'a) list -> 'a let rec lookup dv (k: string) = function | [] -> dv | (k', v) :: xs -> if k = k' then v else lookup dv k xs 1/ update : string -> 'a -> (string * 'a) list -> (string * 'a) list let rec update (k : string) v = function | [] -> [(k, v)] (k', ) as p :: xs-> if k = k' then (k, v) :: xs else p :: update k v xs (i) Implement a function count : string -> string list -> int such that count x xs is the number of times the string x appears in the list xs. > count "x" ["y","z"];; val it : int = 0 > count "x" ["x","x":"x"];; val it : int = 3 > count "x" ["y":"x","x";"z";"y"; "y") ;; val it : int = 2 (ii) The following function traverses its input list twice: // modify: 'a-> ('a -> 'a) -> string -> (string * 'a) list -> (string * 'a) list let modify d f x xs = update x (f (lookup d x xs)) xs Reimplement modify so that the list is traversed at most once. (iii) Using modify, implement a function ac : (string * int) list -> string list -> (string * int) list that adds the number of times each string appears in the second list. Your function should satisfy lookup Ox (ac dict xs) = lookup 0 x dict + count x xs for all dict, x, xs. > ac [] ["x":"x""y":"x"; "y") ;; val it : (string * int) list = [("x", 3); ("y", 2)] > ac [("x", 2); ("y",3)) ["x";"y";"z"];; val it : (string * int) list = [("x", 3); ("y", 4); ("z", 1)] > ac [("x", 2);("y",3)) ["x";"x";"x"];; val it : (string * int) list = [("x", 5); ("y", 3)]
