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.

up vote 6 down vote accepted

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

  • 1
    a cons list is basically a stack – jk. Dec 7 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 at 10:20
  • By the way, why are lists not double linked? – Gábor Angyal Dec 7 at 10:21
  • f#/Haskell lists are immutable - doubly linked lists usually require mutating pointers – jk. Dec 7 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 at 10:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.