# List asymetry in F#

I am trying out F# for the first time with little prior theoretical functional programming knowledge.

I have written a small function so calculate simple moving average on a list. Here it is:

``````let rec sma n data =
let length = List.length data
if length < n then data
else (sma n data.[..length-2]) @ [List.average data.[length - n .. ]]
``````

I was not really satisfied with this result. It looks clumsy, and I have expected a more elegant solution, but could not find one. Then I had a wild idea, and did it backwards. I have calculated SMA by starting at the and of the list moving to the front:

``````let rec sma n data =
if List.length data < n then data
else List.average data.[.. n-1] :: sma n data.Tail
``````

Thats more like it, that is what I have expected. But why can not I do it iterating from the beginning?

According to the F# documentation (https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/lists), I can easily refer to the first element of the list (`Head`) and to the rest of the list (`Tail`), and I can use the `::` operator to create a list by appending a new element at the beginning. However, I do not have a similar way to refer to the last element, or to the list without the last element, nor have I an operator for creating a list by adding a new element to the end.

Why is there this asymmetry? I have learned a little Haskell back in the university, and I think it was symmetric from perspective.

because a cons lists are inherently asymmetric

a :: b :: c :: []

is actually

a :: (b :: (c :: []))

getting at the first/head is an O(1) operation getting at the last item is O(n) and if the list is infinite it won't even finish.

you must be mis-remembering your Haskell I think as this is pretty much the same in Haskell

• a cons list is basically a stack – jk. Dec 7 '18 at 10:14
• You are right, I have checked Haskell docs. Although it does have `last` and `init` functions for lists, it states that they might be slow for long lists. And that is because, I persume, that the list is single linked. – Gábor Angyal Dec 7 '18 at 10:20
• By the way, why are lists not double linked? – Gábor Angyal Dec 7 '18 at 10:21
• f#/Haskell lists are immutable - doubly linked lists usually require mutating pointers – jk. Dec 7 '18 at 10:23
• Thanks. And what would be the "best practise" here? Should I just iterate lists backwards? Or use some different data structure? – Gábor Angyal Dec 7 '18 at 10:26