In functional languages, such as Haskell, where list is a recursive datatype of the form List[x] → EmptyList[x] | x:List[x], structural induction over a list may be expressed with pattern matching like so :
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
But in the Wolfram Language, though the First and Rest functions are available on lists, as I understand it, List is not a recursively organized structure, but rather a flat array of substructures (probably with O(1) access time at a random position in the list).
How then does one go about writing the analogue of the Haskell foldr HOF ? Mimicking structural induction over recursively defined Lists, one could go like this :
But is there some more idiomatic or preferred, or more efficient way of doing this ?
Thanks a lot for your help.
Just as an aside, using a right associative operator for f visually makes plain the difference between foldr and Fold :
