Value of the last element of a list

Question

how to get the value of the last element of a List? I've noted that List.hd (or .Head) return an item, while List.tl (or .Tail) returns a List.

Is rev the List and get the hd the only way around? Thanks.

Selfdenial

Answer 1

Try this function. It uses recursion, though it gets optimised to iteration anyway since it's tail recursion. In any case, it is most likely quicker than reversing the entire list (using List.rev).

let rec last = function
    | hd :: [] -> hd
    | hd :: tl -> last tl
    | _ -> failwith "Empty list."

The answer of Pavel Minaev is definitely worth taking into account, however. Nonetheless, the algorithm you have requested may be useful in some rare cases, and is the most efficient way to go about the task.

Gangplank

Since this is a tail recursive algorithm, the compiler will implement it as an efficient while loop. I tend to agree with Pavel regarding choice of data structure, but if you need to use a list then this is the right approach. – Ottillia

@dahlbyk: Exactly. I meant to make a note about that, but it looks like I forgot - I shall add it now. – Gangplank

it must be "let rec last tl = function", function last has no parameter – Cooperman

Answer 2

In general, if you need to do this, you're doing something wrong. Since F# lists are single-linked, accessing the last element is costly - O(N), where N is size of list. Try to rewrite your algorithm so that you always access the first element, not the last (which is O(1)). If you cannot do so, chances are good that your choice of list for a data structure wasn't correct in the first place.

Astatic

Answer 3

A quick & dirty way of doing it is by using List.reduce. Assuming the list is called ls,

let lastElement ls = List.reduce (fun _ i -> i) ls

As for efficiency, I agree with Pavel.

Pone

Answer 4

A more concise version based on Mitch's answer:

let lastItem = myList |> List.rev |> List.head

The myList list is sent to List.rev function. The result is then processed by List.head

Dissuasion

Answer 5

Agreed, not so efficient to get the last element of list, or any other "enumerable" sequence. That said, this function already exists in the Seq module, Seq.last.

Seaquake

And even if it didn't, it's easily defined: module Seq = let last xs = Seq.reduce (fun _ x -> x) xs – Angle

Answer 6

As a novice F# developer, I don't see what the harm is in doing the following

let mylist = [1;2;3;4;5]

let lastValue = mylist.[mylist.Length - 1]

Imperative in nature? Yes but no need for recursion.

Doornail

This will take a reasonably long time as List.length requires traversing the list, as does the access. Essentially you have to traverse the list twice. – Kernite

I just checked the source code, you are correct. Why a property computers this value however, is beyond me. Perhaps I expected lists to have the same behavior as arrays when knowing about the number of elements. – Doornail

Lists don't cache their size - this reduces their size in memory significantly, as you need to cache the size at every element. – Kernite

By size do you mean length? I was under the impression that a list has an array as a backing store which creates a new array and copies the elements across when the size exceeds its capacity. – Doornail

The lists with an array as a backing store are System.Collections.Generic.List<_>, these are not the same as the F# lists, and have different performance goals. – Kernite

Answer 7

The regular way to work with lists in F# is to use recursion. The first item in a list is the head (obviously) and the rest of the list is the tail (as oppose to the last item). So when a function recieves a list it processes the head and then recursively processes the rest of the list (the tail).

let reversedList = List.rev originalList
let tailItem = List.hd reversedList

Nutriment

Answer 8

I think you can just write

list.[0..list.Length-1]

Chivers

Answer 9

You can call List.Head to get the first element of a list, such that the below expression evaluates to true:

let lst = [1;2;3;4;5]
List.head lst = 1

However, calling List.Tail will return every element in the list after the first element, such that the below expression is true:

let lst = [1;2;3;4;5]
List.tail lst = [2;3;4;5]

Like some other people have mentioned, there isn't an efficient way in F# to get the tail end of a list, basic lists just aren't built with that functionality in mind. If you really want to get the last element you're going to have to reverse your list first, and then take the new head (which was the previous tail).

let lst = [1;2;3;4;5]
(List.head (List.rev lst) ) = 5

Alodee

Answer 10

Below code worked fine with me, I've an array of integers, want to start from the 5th item, then take it minus the item number

Sum of [Array(xi) - Array(xi-5)] where i start at 5

The code used is:

series |> Array.windowed 5
       |> Array.fold (fun s x -> 
                            (x |> Array.rev |> Array.head) -  (x |> Array.head) + s) 0
       |> float

Escadrille

Answer 11

It's a very old question, but just in case someone comes here:

with FSharp 5, you can do x.[^index] where index will start at the end of the array / list.

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

a.[^0] is 9
a.[^1] is 8
etc

Nikaniki

That's a nice feature, but I also wonder if this too traverses the list twice. That doesn't mean this feature is bad of course, but perhaps not optimal for retrieving the last element. – Chlorite

Unless the store the list length; I haven’t looked at the implementation but it’s definitely a valid concern – Nikaniki