Value of the last element of a list
Solution 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.
Solution 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.
Solution 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.
Solution 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
Solution 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
.
Related videos on Youtube
pistacchio
Updated on February 20, 2021Comments
-
pistacchio about 3 years
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.
-
dahlbyk over 14 yearsSince 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.
-
Noldorin over 14 years@dahlbyk: Exactly. I meant to make a note about that, but it looks like I forgot - I shall add it now.
-
Racooon almost 10 yearsit must be "let rec last tl = function", function last has no parameter
-
arash maleki over 9 yearsThis 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. -
Razor over 9 yearsI 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.
-
arash maleki over 9 yearsLists don't cache their size - this reduces their size in memory significantly, as you need to cache the size at every element.
-
Razor over 9 yearsBy 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.
-
arash maleki over 9 yearsThe 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. -
kaefer over 9 yearsAnd even if it didn't, it's easily defined:
module Seq = let last xs = Seq.reduce (fun _ x -> x) xs
-
Bent Tranberg about 3 yearsThat'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.
-
Thomas about 3 yearsUnless the store the list length; I haven’t looked at the implementation but it’s definitely a valid concern