Блог

Главная - Вопросы по программированию - Размещение нового элемента в начале списка

Размещение нового элемента в начале списка

#haskell #recursion

Вопрос:

Эй, Ребята! Так что моя проблема в том, что я не вижу ничего плохого в этом коде.

 type Name = String

type Val = Either Int Bool
type Env = [(Name, Val)]    

update :: Name -> Val -> Env -> Env -> Env
    update x v [] origi = (x,v): origi
    update x v ((x', v'):xs) origi
      | x == x'   = (x, v):xs
      | otherwise = (x', v') : update x v xs origi

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

Итак, что я хочу здесь сделать. Обновляет элементы в списке, которые там есть. Но если их нет в списке. Я хочу положить их в начало. Поставить их в конце было бы легко, я знаю.

Комментарии:

1. Почему существует два Env параметра? Я ожидал бы только одного.

2. Один предназначен для проверки исходного lsit, а другой-для просмотра списка элемент за элементом

3. Я не думаю, что это должно быть частью внешнего интерфейса функции. Он может обрабатывать эту деталь внутренне с помощью вспомогательной функции.

4. Я не понимаю этого, извините 🙁

5. Так должен ли я просто пропустить сохранение исходного списка в переменной?

Ответ №1:

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

 update :: Name -> Val -> Env -> Env

Простая реализация была бы

 import Data.Maybe (fromMaybe)

update :: Name -> Val -> Env -> Env
update name val env = 
    let newEnvIfAbsent = (name, val) : env
        tryToModify list = case list of
            [] -> Nothing
            (name', val') : rest -> if name' == name 
                                    then Just $ (name, val) : rest
                                    else fmap ((name', val') :) $ tryToModify rest
    in fromMaybe newEnvIfAbsent $ tryToModify env

Неофициально мы пытаемся изменить env , найдя пару формы (name : val') и заменив ее на (name, val) . Если это не удастся, мы вместо этого добавим (name, val) в начало env .

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

 update name val env =
    let newEnvIfAbsent = (name, val) : env
        tryToModify list = case list of
            [] -> ([], False)
            (name', val') : rest -> if name' == name
                                    then ((name, val) : rest, True)
                                    else let (rem, suc) = tryToModify rest
                                          in ((name', val') : rem, suc)
        (modifyResult, succeeded) = tryToModify env
    in if succeeded then modifyResult else newEnvIfAbsent

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

Метки: