Что такое список в функциональных языках программирования?

Отвечу за Haskell.
Вот список:
data [a] = [] | a : [a]
Т.е. список либо пуст, либо имеет [ссылку на] [недовычисленную] голову и [ссылку на] [недовычисленный] другой список - хвост. Т.о. чтобы пробежаться по списку (без использования готовых функций), надо проверять, не является ли он пустым, если нет, работать с головой, а хвост обрабатывать рекурсивно.
Список иммутабельный, т.е. ничего никуда вставить нельзя, однако списки могут "шарить" общий хвост, например:

list1 = [2,3,4]
list2 = 1 : 2 : list1
list3 = 0 : 0 : list1

В памяти будет (после форсирования, рассмотрение ленивости я опускаю) как-то так:

1-2
   \
    2-3-4
   /
0-0

Не знаю что такое список в других языках, в Erlang вы можете работать только с головой списка. Вы не можете адресовать произвольный элемент из списка.

Хранится поэлементно, где каждый элемент указывает на следующий элемент в списке (односвязный список).

В чисто функциональных языках программирования функция это одновременно и программа и данные, поэтому список это просто функция которая содержит в себе множество других функций, которые являются элементами списка, в упорядоченном виде. Соответственно извлечь функцию-элемент списка из функции-списка можно с помощью применения функции извлечения функции-элемента списка из функции-списка. В памяти такая конструкция хранится в виде дерева.

Например, функция-список λfx.fu(fv(fwx)) содержит в себе функции-элементы u, v, w

λfx.fu(fv(fwx))

        f
        x
       . .
      f u .
         . .
        f v .
           . .
          f w .
               x

Функция λl.l(λab.a) извлекает первую функцию-элемент из функции-списка

λl.l(λab.a)

         l
        l a
          b
          a

Извлечение функции-элемента u из функции-списка (λl.l(λab.a))(λfx.fu(fv(fwx)))

(λl.l(λab.a))(λfx.fu(fv(fwx)))x = u

                                                                         .
      .                  .            x             x            x      x x    u
     . .                . .          . .           . .           u      u
    l   .              f   a        a u .         b   .
   l a   .             x   b        b  . .        u  . .
     b   f            . .  a        a a v .         b   .
     a   x           f u .            b  . .        v  . .
        . .             . .           a a w .         b   x
       f u .           f v .            b    x        w
          . .             . .           a
         f v .           f w .
            . .               x
           f w .
                x