Объединение и замена

В Haskell я определил полиморфный тип данных Subst a с одним конструктором S :: [(String, a)] -> Subst a следующим образом:

data Subst a where
    S :: [(String, a)] -> Subst a
    deriving (Show)

Я хочу определить функцию get::String -> Subst a -> Maybe a, которая принимает имя переменной и подстановку и возвращает значение, которое эта переменная должна заменить. Если подстановка не определена для переменной, функция не должна возвращать ничего.

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

get :: String -> Subst a -> Maybe a
get str (S[]) = Nothing
get str (S((a,b):xs)) = if str == a then Just b
    else get str xs

Но я получаю ошибки. Есть идеи, почему?


substitution haskell unification
person NuNu    schedule 07.11.2012    source источник
comment
Есть ли у вас какие-либо причины для использования синтаксиса GADT? Не могли бы вы написать свой тип проще как data Subst a = S [(String, a)] deriving Show?   -  person Tikhon Jelvis    schedule 07.11.2012
comment
@ Тихон, на самом деле, нет особой причины, я пытался использовать оба способа в качестве механизма обучения, чтобы увидеть, отличается ли он   -  person NuNu    schedule 07.11.2012
comment
Я бы предложил использовать Map String a вместо [(String,a)]. Поиск списков занимает O(n), а поиск карты занимают O(log n).   -  person Petr    schedule 07.11.2012
comment
+1 за предложение @PetrPudlák. Даже если вы не заботитесь о производительности, тип Map a b имеет очень богатый API для поиска и вставки.   -  person Paul R    schedule 07.11.2012

Ответы (1)


arrow_upward
4
arrow_downward 

get str (S((a,b):xs)) = if str == a then Just b
    else get str xs

xs — это список типа [(String, a)], но второй аргумент get должен быть Subst a. Это сработало бы, если бы вы использовали конструктор для создания значения правильного типа,

get str (S((a,b):xs)) = if str == a then Just b
    else get str (S xs)

но проще использовать список напрямую для поиска переменной,

Prelude> :t lookup
lookup :: Eq a => a -> [(a, b)] -> Maybe b

so

get str (S xs) = lookup str xs

делает именно то, что вы хотите.

person Daniel Fischer    schedule 07.11.2012
comment
Благодарность! Первоначально я использовал функцию поиска, но она выдавала мне ошибки, поэтому я попытался написать свою собственную, но спасибо, что прояснили это! - person NuNu; 07.11.2012