F#: killing redundancy in Map/Reduce/Filter

Question

Let's say I have a list and a set and I want to do some stuff with them:

let outA = inA |> List.map(fun x -> x + 1) |> List.filter(fun x -> x > 10)
let outB = inB |> Set.map(fun x -> x + 1) |> Set.filter(fun x -> x > 10)

Now, obviously A handles lists and B handles sets. However, I find it very annoying to have to write List. List. over and over again: not only is it verbose, repetitive boilerplate which conveys no information and gets in the way of reading the functionality of the code, it is also a de-facto type annotation which I have to keep track of and keep in sync with the rest of my code.

What I want to be able to do is something like the following:

let outA = inA |> map(fun x -> x + 1) |> filter(fun x -> x > 10)
let outB = inB |> map(fun x -> x + 1) |> filter(fun x -> x > 10)

With the compiler knowing that inA is a list and inB is a set, and thus all the operations are from the correct class, and therefore outA is a list and outB is a set. I can partially achieve this with Seq:

let map(x) =
    Seq.map(x)

let filter(x) =
    Seq.filter(x)

And I can write exactly that. The problem with this is that it casts everything into Sequences, and I can no longer perform list/set operations on them. Similarly,

let outA = inA.Select(fun x -> x + 1).Where(fun x -> x > 10)
let outB = inB.Select(fun x -> x + 1).Where(fun x -> x > 10)

Also removes all that, but then casts everything to IEnumerable. I managed to get it pretty nice by converting all the static methods into instance methods via extensions:

type Microsoft.FSharp.Collections.List<'a> with
    member this.map(f) = this |> List.map(f)
    member this.filter(f) = this |> List.filter(f)

let b = a.map(fun x -> x + 1).filter(fun x -> x > 10)

but I suspect that will run into the type-inference problems mentioned here: Method Chaining vs |> Pipe Operator? I'm don't really know; I'm not familiar with how the type inference algorithm works.

The bottom line is, I figure I'm going to be doing a hell lot of these list/set/array map/reduce/filter operations and I want to make them look as pretty and clean as possible. Right now, apart from distracting me from the important bits in the expression (i.e. the "map" and the lambda) they also provide de-facto type annotations in a place where the compiler should jolly-well-know what the collection i'm passing in is.

Furthermore, this is exactly the sort of thing that OO inheritance and polymorphism is meant to solve, so I was wondering if there was some equivalent functional pattern that I do not know that would solve it just as elegantly. Perhaps I could do a type check in my own static map and perform the relevant type's map function on the input?

Does anyone have any better solution than those I've already tried, or am I bumping my head into a fundamental limitation of the F# type inference engine, that I should just accept and move on?

Answer 1

This is not the thing OO/inheritance/polymorphism solves. Rather it is the thing 'type classes' (a la Haskell) solve. The .NET type system is not capable of doing type classes, and F# doesn't try to add that capability. (You can do some hairy tricks with inline, but it has various limitations.)

I recommend accepting it and moving on.

Answer 2

I agree with Brian - you'll simply get used to this. As I mentioned in the answer to your previous question, this is sometimes quite useful, because you'll see what your code does (which part evaluates lazily, which part uses arrays for efficiency etc.)

Also, some functions are only available for some types - for example there is List.tail or List.foldBack, but similar functions don't exist for IEnumerable (in the Seq module) - for good reasons as they would lead to bad code.

In Haskell, type classes can describe types that have some functions (like map and filter), but I don't think they scale very well - to specify type classes for the F# library, you would end up with a hierarchy of type classes that specify list-like data structures, list-like data structures with tail and foldBack-like functions and too many other constraints.

Aside, for many simple list processing jobs, you can also use comprehensions which give you a lot nicer syntax (but of course, it is only useful for basic things):

let outB = seq { for x in inA do 
                   if x > 10 do yield x + 1 }