How to implement the list filter function in F# using primitives

Question

I was reading Why functional programming matters where the author implements a couple of applications using foldr and function composition. I did the some of them in F# e.g. the map function:

let cons a lst = a::lst
let map f lst = List.foldBack (f>>cons) lst []

Then I wanted to implement the list filter function and got stuck:

let filter pred lst = List.foldBack (what-goes-here?) lst []

The what-goes-here? function should take as input a list item, the accumulating filtered list and return the same list if the predicate returns false and a cons:ed list if it returns true.

I guess I need the option type here but can't figure out how to glue things together. Is it possible to compose a function using pred and cons (and perhaps some other primitives) to achieve this without writing a custom lambda function which does all the plumbing? Is this a case for computation expressions?

Answer 1

A pragmatic answer to your question is:

whatGoesHere = fun x xs -> if f x then x :: xs else xs

Anonymous functions, if-then-else and lists are all considered primitives by F# practitioners. This is the clearest, most maintainable way to write this code.

Alas, you have not accepted the equivalent correct answer from the previous responder, and you insist on seeing code involving no lambda expressions. You are welcome:

``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s
`k`s`k``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ks``s`kki
`ki`k`ki``s``s`ks``s`kki`ki
`k``s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`s`ks
``s`k`s`kk``s`k`si``s`kki`k``s``s`ks
``s`k`s`ks``s`k`s`kk``s``s`ks``s`kki`ki
`k`kii`ki`k`ki

The above is whatGoesHere in SKI combinator calculus using a suitable representation of booleans and lists, printed in Unlambda notation.

For your convenience, here is a sample compiler from untyped lambda calculus to SKI combinators, and the F# definitions of lambda calculus terms corresponding to your problem:

http://gist.github.com/3277850

While the equivalence of combinatory logic and lambda calculus makes lambda expressions unnecessary in theory, they are indispensable for expressing your intent as a programmer. "Why functional programming matters" in no way advocates avoiding lambda expressions and helper functions. To the contrary - the ability to define functions, including higher-order functions, is at the very core of functional programming. It hardly matters whether the functions are defined by composition or explicitly use lambda calculus: both are the "glue" the paper talks about.

I suggest you give the paper (and perhaps its excellent references) another read, and then install Haskell or Clean. Given that the authors advocate pure lazy-by-default evaluation model, F# is not a good platform to explore these ideas.

Answer 2

let consT pred a lst = if pred a then a::lst else lst
let filter pred lst = List.foldBack (consT pred) lst []