In which functional programming function would one grow a set of items?

Which of the three (if any (please provide an alternative)) would be used to add elements to a list of items?

• Fold
• Map
• Filter

Also; how would it开发者_高级运维ems be added? (appended to the end / inserted after working item / other)

---

A list in functional programming is usually defined as a recursive data structure that is either a special empty value, or is composed of a value (dubbed "head") and another list (dubbed "tail"). In Haskell:

-- A* = 1 + A x A*
-- there is a builtin list type:
data [a] = [] | (a : [a])

To add an element at the head, you can use "cons": the function that takes a head and a tail, and produces the corresponding list.

-- (:) is "cons" in Haskell
(:) :: a -> [a] -> [a]

x = [1,2,3]   -- this is short for (1:(2:(3:[])))
y = 0 : x     -- y = [0,1,2,3]

To add elements at the end, you need to recurse down the list to add it. You can do this easily with a fold.

consAtEnd :: a -> [a] -> [a]
consAtEnd x = foldr [x] (:)
    -- this "rebuilds" the whole list with cons,
    -- but uses [x] in the place of []
    -- effectively adding to the end

To add elements in the middle, you need to use a similar strategy:

consAt :: Int -> a -> [a] -> [a]
consAt n x l = consAtEnd (take n l) ++ drop n l
     -- ++ is the concatenation operator: it joins two lists
     -- into one.
     -- take picks the first n elements of a list
     -- drop picks all but the first n elements of a list

Notice that except for insertions at the head, these operations cross the whole list, which may become a performance issue.

---

"cons" is the low-level operation used in most functional programming languages to construct various data structure including lists. In lispy syntax it looks like this:

(cons 0 (cons 1 (cons 2 (cons 3 nil))))

Visually this is a linked list

0 -> 1 -> 2 -> 3 -> nil

Or perhaps more accurately

cons -- cons -- cons -- cons -- nil
  |       |       |       |
  0       1       2       3

Of course you could construct various "tree"-like data structures with cons as well.

A tree like structure might look something like this

(cons (cons 1 2) (cons 3 4))

I.e. Visually:

  cons
  /  \
cons cons
/ \   / \
1 2   3 4

However most functional programming languages will provide many "higher level" functions for manipulating lists.

For example, in Haskell there's

• Append: (++) :: [a] -> [a] -> [a]
• List comprehension: [foo c | c <- s]
• Cons: (:) :: a -> [a] -> [a] (as Martinho already mentioned)
• And many many more

Just to offer a concluding remark, you wouldn't often operate on individual elements in a list in the way that you're probably thinking, this is an imperative mindset. You're more likely to copy the entire structure using a recursive function or something in that line. The compiler/virtual machine is responsible recognizing when the memory can be modified in place and updating pointers etc.