F# return list of list lengths

Question

I am to use combinators and no for/while loops, recursion or defined library functions from F#'s List module, except constructors :: and []

Ideally I want to implement map

I am trying to write a function called llength that returns the list of the lengths of the sublists. For example llength [[1;2;3];[1;2];[1;2;3]] should return [3;2,3]. I also have function length that returns the length of a list.

let Tuple f = fun a b -> f (a, b)
let length l : int =
    List.fold (Tuple (fst >> (+) 1)) 0 l

currently have

let llength l : int list =
    List.map (length inner list) list

Not sure how I should try accessing my sublists with my restraints and should I use my other method on each sublist? any help is greatly appreciated, thanks!

Answer 1

Since this is homework, I don't want to just give you a fully coded solution, but here are some hints:

First, since fold is allowed you could implement map via fold. The folding function would take the list accumulated "so far" and prepend the next element transformed with mapping function. The result will come out reversed though (fold traverses forward, but you prepend at every step), so perhaps that wouldn't work for you if you're not allowed List.rev.

Second - the most obvious, fundamental way: naked recursion. Here's the way to think about it: (1) when the argument is an empty list, result should be an empty list; (2) when the argument is a non-empty list, the result should be length of the argument's head prepended to the list of lengths of the argument's tail, which can be calculated recursively. Try to write that down in F#, and there will be your solution.

Answer 2

Since you can use some functions that basically have a loop (fold, filter ...), there might be some "cheated & dirty" ways to implement map. For example, via filter:

let mymap f xs =
    let mutable result = []
    xs
    |> List.filter (fun x ->
        result <- f x :: result
        true)
    |> ignore
    result |> List.rev

Note that List.rev is required as explained in the other answer.