zahardzhan

Гёдель, Эшер, Бах: эта бесконечная гирлянда. Хофштадтер, 1979.

Если смотреть на вещи проще, то функция в программировании - это правила, по которым из чего-то одного получается что-то другое (причем это что-то другое всегда одинаковое для одного и того же).

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

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

Например, функция-список λ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