CODEWITHSUNDEEP
f#iterationsublist
Code Guy
Code Guy

Reputation: 197

Sorting indexes in list of lists - F#

Currently I have a function to return the first elements of each list (floats), within a list to a separate list.

let firstElements list =
    match list with
    | head::_ -> head
    | [] -> 0.00

My question is, how do I expand this to return elements at the same index into different lists while I don't know how long this list is? For example

let biglist = [[1;2;3];[4;5;6];[7;8;9]]

If I did not know the length of this list, what is the most efficient and safest way to get 

[[1;4;7];[2;5;8];[3;6;9]]

Upvotes: 2

Views: 676

Answers (2)

David Raab
David Raab

Reputation: 4488

You can use the recent added List.transpose function. But it is always good to be good enough to create such functions yourself. If you want to solve the problem yourself, think of a general algorithm to solve your problem. One would be.

  1. From the first element of each list you create a new list
  2. You drop the first element of each list
  3. If you end with empty lists you end, otherwise repeat at step 1)

This could be the first attempt to solve the Problem. Function names are made up, at this point.

let transpose lst =
    if allEmpty lst 
    then // Some Default value, we don't know yet
    else ...

The else branch looks like following. First we want to pick the first element of every element. We imagine a function pickFirsts that do this task. So we could write pickFirsts lst. The result is a list that itself is the first element of a new list.

The new list is the result of the remaining list. First we imagine again a function that drops the first element of every sub-list dropFirsts lst. On that list we need to repeat step 1). We do that by a recursive call to transpose. Overall we get:

let rec transpose lst =
     if   allEmpty lst
     then // Some Default value, we don't know yet
     else (pickFirsts lst) :: (transpose (dropFirsts lst))

At this point we can think of the default value. transpose needs to return a value in the case it ends up with an empty list of empty lists. As we use the result of transpose to add an element to it. The results of it must be a list. And the best default value is an empty list. So we end up with.

let rec transpose lst =
    if   allEmpty lst
    then []
    else (pickFirsts lst) :: (transpose (dropFirsts lst))

Next we need to implement the remaining functions allEmpty, pickFirsts and dropFirsts.

pickFirst is easy. We need to iterate over each element, and must return the first value. We get the first value of a list by List.head, and iterating over it and turning every element into a new list is what List.map does.

let pickFirsts lst = List.map List.head lst

dropFirsts need to iterate ver each element, and just remove the first element, or in other words keeps the remaining/tail of a list.

let dropFirsts lst = List.map List.tail lst

The remaining allEmpty is a predicate that either return true/false if we have an empty list of lists or not. With a return value of bool, we need another function that allows to return another type is a list. This is usually the reason to use List.fold. An implementation could look like this:

let allEmpty lst   = 
    let folder acc x =
        match x with
        | [] -> acc
        | _  -> false
    List.fold folder true lst

It starts with true as the default value. As long it finds empty lists it returns the default value unchanged. As soon there is one element found, in any list, it will return false (Not Empty) as the new default value.

The whole code:

let allEmpty lst   = 
    let folder acc x =
        match x with
        | [] -> acc
        | _  -> false
    List.fold folder true lst

let pickFirsts lst = List.map List.head lst
let dropFirsts lst = List.map List.tail lst


let rec transpose lst =
    if   allEmpty lst
    then []
    else (pickFirsts lst) :: (transpose (dropFirsts lst))


transpose [[1;2;3];[4;5;6];[7;8;9]]

Another approach would be to turn it into a 2 dimensional mutable array. Also do length checkings. Do the transformation and return the mutable array again as an immutable list.

Upvotes: 2

Szer
Szer

Reputation: 3476

List.transpose has been added recently to FSharp.Core

let biglist = [[1;2;3];[4;5;6];[7;8;9]]

let res = biglist |> List.transpose

//val res : int list list = [[1; 4; 7]; [2; 5; 8]; [3; 6; 9]]

Upvotes: 3

Related Questions