Создание таблицы для хранения данных в Haskell

Question

Я пытаюсь хранить данные в стиле ключевого значения в Haskell. Идея состоит в том, что у меня есть идентификатор (Ident), и это может быть одно значение или список из них.

Я попробовал следующую структуру:

type Ident = String 
data SymTable a = ST [(Ident, Either a [a])] 
        deriving (Show) 

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

setVar :: SymTable a -> Ident -> Either a [a] -> SymTable a 
getVar :: SymTable a -> Ident -> Either a [a] 

Я попробовал несколько реализаций, но я не могу заставить компилятор работать (принимать типы).

В качестве ограничения я не могу использовать какую-либо внешнюю библиотеку (нет Карты или аналогий).

UPDATE

Так что моя идея состояла в том, чтобы сделать что-то вроде этого:

setVar :: SymTable a -> Ident -> Either a [a] -> SymTable a 
setVar (ST xs) i a = ST ([(i, a)] ++ xs) 

getVar :: SymTable a -> Ident -> Either a [a] 
getVar t i = snd (head (filter (\x -> fst x == i) t)) 

UPDATE 2

После @freestyle ответа, я немного изменился SetVar, так что если вы введите идентификатор, который уже существует, он перезаписывает его.

setVar :: SymTable a -> Ident -> Either a [a] -> SymTable a 
setVar (ST xs) i a = ST ([(i, a)] ++ clearList xs i) 
    where 
     clearList [] _ = [] 
     clearList (x:xs) i 
      | fst x == i = clearList xs i 
      | otherwise = x : clearList xs i 

GETVAR остается, как он предложил:

getVar :: SymTable a -> Ident -> Maybe (Either a [a]) 
getVar (ST xs) i = lookup i xs 

Answer 1

Я не вижу никаких проблем с составлением setVar, но более лучше setVar (ST xs) i a = ST ((i, a) : xs).

У вас возникли проблемы с getVar. filter может «съесть» список, но вы дали SymTable.

Таким образом, вы можете сделать так:

getVar (ST xs) i = snd (head (filter (\x -> fst x == i) xs)) 

Более лучший способ:

getVar (ST xs) i = fromJust (lookup i xs) 

Но, если ключ не существует, вы получите исключение. Итак, возможно, вы хотите:

getVar :: SymTable a -> Ident -> Maybe (Either a [a]) 
getVar (ST xs) i = lookup i xs