Return item at position x in a list

I was reading this post While or Tail Recursion in F#, what to开发者_如何学运维 use when? were several people say that the 'functional way' of doing things is by using maps/folds and higher order functions instead of recursing and looping.

I have this function that returns the item at position x in a list:

let rec getPos l c =  if c = 0 then List.head l else getPos (List.tail l) (c - 1)

how can it be converted to be more functional?

This is a primitive list function (also known as List.nth).

It is okay to use recursion, especially when creating the basic building blocks. Although it would be nicer with pattern matching instead of if-else, like this:

let rec getPos l c =
   match l with
   | h::_ when c = 0 -> h
   | _::t -> getPos t (c-1)
   | [] -> failwith "list too short"

It is possible to express this function with List.fold, however the result is less clear than the recursive version.

I'm not sure what you mean by more functional.

Are you rolling this yourself as a learning exercise?

If not, you could just try this:

> let mylist = [1;2;3;4];;
> let n = 2;;
> mylist.[n];;

Your definition is already pretty functional since it uses a tail-recursive function instead of an imperative loop construct. However, it also looks like something a Scheme programmer might have written because you're using head and tail.

I suspect you're really asking how to write it in a more idiomatic ML style. The answer is to use pattern matching:

let rec getPos list n =
    match list with
    | hd::tl ->
        if n = 0 then hd
        else getPos tl (n - 1)
    | [] -> failWith "Index out of range."

The recursion on the structure of the list is now revealed in the code. You also get a warning if the pattern matching is non-exhaustive so you're forced to deal with the index too big error.

You're right that functional programming also encourages the use of combinators like map or fold (so called points-free style). But too much of it just leads to unreadable code. I don't think it's warranted in this case.

Of course, Benjol is right, in practice you would just write mylist.[n].

If you'd like to use high-order functions for this, you could do:

let nth n = Seq.take (n+1) >> Seq.fold (fun _ x -> Some x) None

let nth n = Seq.take (n+1) >> Seq.reduce (fun _ x -> x)

But the idea is really to have basic constructions and combine them build whatever you want. Getting the nth element of a sequence is clearly a basic block that you should use. If you want the nth item, as Benjol mentioned, do myList.[n].

For building basic constructions, there's nothing wrong to use recursion or mutable loops (and often, you have to do it this way).

Not as a practical solution, but as an exercise, here is one of the ways to express nth via foldr or, in F# terms, List.foldBack:

let myNth n xs =
    let step e f = function |0 -> e |n -> f (n-1)
    let error _ = failwith "List is too short"
    List.foldBack step xs error n