A question concerning list accesses from a noobie functional programmer?

Because lists are by design a linear structure. They are the canonical recursive data type, defined as: data a = | a : a That is, either the empty list, or a cons node, consisting of an element, and a tail, which is also a list This structure precisely corresponds to inductive definitions in mathematics, and correspondingly, makes it trivial to write many functions as simple recursive calls The recursive data type does not admit random access in non-linear time, however. For that you need hardware support (which we all have), and a more sophisticated data type (or less sophisticated, depending on your viewpoint) Summary : lists are computer science's encoding of induction as a recursive data structure.It's fundamental, you need it, but it doesn't do random access.

Because lists are by design a linear structure. They are the canonical recursive data type, defined as: data a = | a : a That is, either the empty list, or a cons node, consisting of an element, and a tail, which is also a list. This structure precisely corresponds to inductive definitions in mathematics, and correspondingly, makes it trivial to write many functions as simple recursive calls.

The recursive data type does not admit random access in non-linear time, however. For that you need hardware support (which we all have), and a more sophisticated data type (or less sophisticated, depending on your viewpoint). Summary: lists are computer science's encoding of induction as a recursive data structure.It's fundamental, you need it, but it doesn't do random access.

In the Java world, java.util. List is an interface (i.e. It's abstract), which is implemented both by a linked list class and an array-backed list class.

That might be the source of the confusion, for some people. – Robin Green May 14 at 8:05 1 « lists are computer science's encoding of induction as a recursive data structure ». I can't make any sense of this.

Other algebraic data structures are also inductive. This doesn't justify why list would be any more "fundamental". I think lists are widely used because we often need to manipulate an unbound number of elements of a type, but your formulation makes it look like there is a deeper reason, while there really isn't.

– gasche May 14 at 9:13 1 @gasche - would you consider the natural numbers as "fundamental"? Lists are just the natural numbers carrying a data item at each element. Data Nat = Zero | Succ Nat cf.

Data List a = Nil | Cons a (List a). – stephen tetley May 14 at 11:16 1 @gasche - unary is simpler, hence more "fundamental". Okasaki starts chapter 9 with the analogy I repeated above, as a prelude to the more complicated binary case.

– stephen tetley May 14 at 11:33 1 I don't want to sound pedantic, but "simpler" and "fundamental" are different concepts. Lists are indeed a "simple" inductive structure (at least among the recursive parametrized ones), but that alone does not make it more "fundamental" than any other. – gasche May 14 at 12:39.

Haskell lists correspond to linked lists in imperative languages; they are inherently sequential since you only have access to the head and need to traverse to find other elements. If you want random access you should choose some other data type. Perhaps from Data.

Array or Data.IntMap.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.