Confused over behavior of List.mapi in F#

Question

I am building some equations in F#, and when working on my polynomial class I found some odd behavior using List.mapi

Basically, each polynomial has an array, so 3*x^2 + 5*x + 6 would be [|6, 5, 3|] in the array, so, when adding polynomials, if one array is longer than the other, then I just need to append the extra elements to the result, and that is where I ran into a problem.

Later I want to generalize it to not always use a float, but that will be after I get more working.

So, the problem is that I expected List.mapi to return a List not individual elements, but, in order to put the lists together I had to put [] around my use of mapi, and I am curious why that is the case.

This is more complicated than I expected, I thought I should be able to just tell it to make a new List starting at a certain index, but I can't find any function for that.

type Polynomial() =
    let mutable coefficients:float [] = Array.empty
    member self.Coefficients with get() = coefficients
    static member (+) (v1:Polynomial, v2:Polynomial) =
        let ret = List.map2(fun c p -> c + p) (List.ofArray v1.Coefficients) (List.ofArray v2.Coefficients)
        let a = List.mapi(fun i x -> x)
        match v1.Coefficients.Length - v2.Coefficients.Length with
            | x when x < 0 ->
                ret :: [((List.ofArray v1.Coefficients) |> a)]
            | x when x > 0 ->
                ret :: [((List.ofArray v2.Coefficients) |> a)]
            | _ -> [ret]

Answer 1

I think that a straightforward implementation using lists and recursion would be simpler in this case. An alternative implementation of the Polynomial class might look roughly like this:

// The type is immutable and takes initial list as constructor argument
type Polynomial(coeffs:float list) = 
  // Local recursive function implementing the addition using lists
  let rec add l1 l2 = 
    match l1, l2 with
    | x::xs, y::ys -> (x+y) :: (add xs ys)
    | rest, [] | [], rest -> rest

  member self.Coefficients = coeffs

  static member (+) (v1:Polynomial, v2:Polynomial) = 
    // Add lists using local function
    let newList = add v1.Coefficients v2.Coefficients
    // Wrap result into new polynomial
    Polynomial(newList)

It is worth noting that you don't really need mutable field in the class, since the + operator creates and returns a new instance of the type, so the type is fully immutable (as you'd usually want in F#).

The nice thing in the add function is that after processing all elements that are available in both lists, you can simply return the tail of the non-empty list as the rest.

---

If you wanted to implement the same functionality using arrays, then it may be better to use a simple for loop (since arrays are, in principle, imperative, the usual imperative patterns are usually the best option for dealing with them). However, I don't think there is any particular reason for preferring arrays (maybe performance, but that would have to be evaluated later during the development).

As Pavel points out, :: operator appends a single element to the front of a list (see the add function above, which demonstrates that). You could write what you wanted using @ which concatenates lists, or using Array.concat (which concatenates a sequence of arrays).

An implementation using higher-order functions and arrays is also possible - the best version I can come up with would look like this:

let add (a1:_[]) (a2:_[]) =
  // Add parts where both arrays have elements
  let l = min a1.Length a2.Length
  let both = Array.map2 (+) a1.[0 .. l-1] a2.[0 .. l-1]  
  // Take the rest of the longer array
  let rest = 
    if a1.Length > a2.Length 
    then a1.[l .. a1.Length - 1] 
    else a2.[l .. a2.Length - 1]
  // Concatenate them
  Array.concat [ both; rest ]

add [| 6; 5; 3 |] [| 7 |]  

This uses slices (e.g. a.[0 .. l]) which give you a part of an array - you can use these to take the parts where both arrays have elements and the remaining part of the longer array.

Answer 2

I think you're misunderstanding what operator :: does. It's not used to concatenate two lists. It's used to prepend a single element to the list. Consequently, it's type is:

'a -> 'a list -> 'a list

In your case, you're giving ret as a first argument, and ret is itself a float list. Consequently, it expects the second argument to be of type float list list - hence why you need to add an extra [] to the second argument to make it to compile - and that will also be the result type of your operator +, which is probably not what you want.

You can use List.concat to concatenate two (or more) lists, but that is inefficient. In your example, I don't see the point of using lists at all - all this converting back & forth is going to be costly. For arrays, you can use Array.append, which is better.

By the way, it's not clear what is the purpose of mapi in your code at all. It's exactly the same as map, except for the index argument, but you're not using it, and your mapping is the identity function, so it's effectively a no-op. What's it about?