Добавление элемента в список, а затем его обратное - PullRequest
Новая
       10

Добавление элемента в список, а затем его обратное

0 голосов
/ 15 ноября 2018

Я изучаю Haskell и пытаюсь понять списки.

Из исследования, чтобы добавить элемент в список, вы обычно делаете: 

let numbers = [4,8,15,16,23,42] 
numbers ++ [56]

но процитировать этот ответ :

Если вам нужно сделать это, обычно есть лучший способ структурировать ваш алгоритм.Например, вы можете построить list в обратном порядке (добавляя элементы в начале) и вызывать только reverse в конце.

Код : 

let numbers = [23,43,56]
let newNumbers = 69:numbers
reverse newNumbers

Вывод : 

[56,43,23,69]

Вопрос :

  1. Правильно ли написан код согласноцитируемый ответ?
  2. Я хочу немного лучше понять терминологию, могу ли я сказать, что я добавляю элементы в head из list?Насколько я понимаю, каждый новый элемент будет первым элементом, и значение будет возвращено, когда я напишу head newNumbers.

1 Ответ

0 голосов
/ 15 ноября 2018

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

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

data Queue a = Queue [a] [a]

-- Put new elements on the incoming list.
addToQueue :: a -> Queue a -> Queue a
addToQueue x (Queue incoming outgoing) = Queue (x:incoming) outgoing

-- Take elements from the outgoing list, whose elements are stored
-- in the reverse order that they were added to the incoming list
-- previously.
removeFromQueue :: Queue a -> (a, Queue a)
removeFromQueue (Queue [] []) = error "Cannot remove from empty queue"
removeFromQueue (Queue incoming (x:xs)) = (x, Queue incoming xs)
removeFromQueue (Queue incoming []) = removeFromQueue (Queue [] (reverse incoming))

(Мы не заинтересованы в хороших способах удаленияиз пустой очереди здесь, просто назовите это ошибкой и оставьте это при этом.)

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

Амортизированный анализ можно использовать, чтобы показать, что хотя reverse может быть медленным, оно уравновешивается количеством быстрых операций, которые предшествуют и могут следовать за ним.

...