В какой функциональной функции программирования можно вырастить набор предметов?

Question

Какой из трех (если есть (укажите альтернативный)) будет использоваться для добавления элементов в список элементов?

• Сгиб
• Карта
• Фильтр

Также; как будут добавлены элементы? (добавляется в конец / вставляется после рабочего элемента / другое)

Answer 1

Список в функциональном программировании обычно определяется как рекурсивная структура данных, которая представляет собой либо специальное пустое значение, либо состоит из значения (названного «головой») и другого списка (дублированного «хвоста»).В Haskell:

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

Чтобы добавить элемент в голову, вы можете использовать «cons»: функцию, которая берет голову и хвост и выдает соответствующий список.

-- (:) 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]

Чтобы добавить элементы в конце, вам нужно свернуть список вниз, чтобы добавить его.Это можно легко сделать с помощью сгиба.

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

Чтобы добавить элементы посередине, вам нужно использовать аналогичную стратегию:

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

Обратите внимание, что за исключением вставок в головеэти операции пересекают весь список, что может стать проблемой производительности.

Answer 2

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

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

Визуально это связанный список

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

Или, возможно, более точно

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

Конечно, вы можете построитьразличные "древовидные" подобные структуры данных с минусами.

Древовидная структура может выглядеть примерно так

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

Т.е. визуально:

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

Однако большинство функциональных языков программирования предоставляют множество функций «более высокого уровня» дляманипулирование списками.

Например, в Haskell есть

• Приложение: (++) :: [a] -> [a] -> [a]
• Понимание списка: [foo c |c <- s] </li>
• Минусы: (:) :: a -> [a] -> [a] (как уже упоминал Мартиньо)
• И много много больше

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