Головоломка соответствия шаблону Haskell

Я пытался выполнить поиск по списку пар, в которых может быть элемент ("$", Undefined) в произвольном месте. Я хотел ТОЛЬКО искать часть списка перед этим специальным элементом, поэтому я попробовал что-то вроде этого (уже есть предназначен для того, чтобы взять элемент n и список xs в качестве аргументов):

checkNotSameScope :: Env -> VarName -> Expr -> Expr
checkNotSameScope (xs:("$", Undefined):_) n e = if alreadyThere n xs then BoolLit False
                                                   else BoolLit True

Но это не работает; компилятор, похоже, указал, что (xs: ..) имеет дело только с ОДНИМ значением, предшествующим моему списку. Я не могу использовать : для указания первого фрагмента списка; только один элемент. Оглядываясь назад, это имеет смысл; иначе как бы компилятор знал, что делать? Добавление «s» к чему-то вроде «x» волшебным образом не создает несколько элементов! Но как я могу обойти это?


list haskell pattern-matching prepend
person norman    schedule 14.10.2012    source источник
comment
Может быть, я должен спросить, как я могу сделать это по-другому, без сопоставления с образцом, поскольку это невозможно? Haskell для очень умных людей.   -  person norman    schedule 14.10.2012

Ответы (3)


arrow_upward
5
arrow_downward

К сожалению, даже с умными компиляторами и языками не избежать некоторых программ...

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

checkNotSameScope :: Env -> VarName -> Expr -> Expr
checkNotSameScope xs n e = if alreadyThere n (takeWhile (/= ("$", Undefined)) xs)
                           then BoolLit False
                           else BoolLit True

Возможно, это не то, что вам нужно для списков, где ("$", Undefined) не встречается, так что будьте осторожны.

person Joachim Breitner    schedule 14.10.2012
comment
Или даже checkNotSameScope xs n e = BoolLit . not . alreadyThere n . takeWhile (/= ("$", Undefined)) $ xs - person pat; 15.10.2012
comment
Верно. Я просто исправлял рассматриваемый код, не читая слишком много остального. - person Joachim Breitner; 16.10.2012

arrow_upward
2
arrow_downward

Подобно ответу Иоахима, вы можете использовать break , что позволит вам определить, когда ("$", Undefined) не происходит (если это необходимо). то есть

checkNotSameScope xs n e = case break (== ("$", Undefined)) xs of
                             (_, [])  -> .. -- ("$", Undefined) didn't occur!
                             (xs', _) -> BoolLit . not $ alreadyThere n xs'

(NB. Вы теряете некоторую лень в этом решении, так как список должен быть пройден до ("$", Undefined) или до конца, чтобы проверить первый случай.)

person huon    schedule 14.10.2012

arrow_upward
1
arrow_downward

Haskell не может выполнять такое сопоставление шаблонов "из коробки", хотя есть некоторые языки, которые могут, например CLIPS, например, или F#, используя активные шаблоны.

Но мы можем использовать существующие возможности сопоставления с образцом в Haskell, чтобы получить аналогичный результат. Давайте сначала определим функцию под названием deconstruct, определяемую следующим образом:

deconstruct :: [a] -> [([a], a, [a])]
deconstruct [] = []
deconstruct [x] = [([], x, [])]
deconstruct (x:xs) = ([], x, xs) : [(x:ys1, y, ys2) | (ys1, y, ys2) <- deconstruct xs]

Что делает эта функция, так это получает все разложения списка xs на тройки формы (ys1, y, ys2) такие, что ys1 ++ [y] ++ ys2 == xs. Так, например:

deconstruct [1..4] => [([],1,[2,3,4]),([1],2,[3,4]),([1,2],3,[4]),([1,2,3],4,[])]

Используя это, вы можете определить свою функцию следующим образом:

checkNotSameScope xs n e =
    case [ys | (ys, ("$", Undefined), _) <- deconstruct xs] of
        [ys] -> BoolLit $ not $ alreadyThere n xs
        _    -> -- handle the case when ("$", Undefined) doesn't occur at all or more than once

Мы можем использовать do-notation, чтобы получить что-то еще более близкое к тому, что вы ищете:

checkNotSameScope xs n e = BoolLit $ not $ any (alreadyThere n) prefixes
    where
        prefixes = do
            (xs, ("$", Undefined), _) <- deconstruct xs
            return xs

Здесь происходит несколько вещей. Во-первых, в переменной prefixes будут храниться все списки префиксов, которые встречаются перед парой ("$", Undefined), или ни одного, если пары нет во входном списке xs. Затем с помощью функции any мы проверяем, дает ли alreadyThere n значение True для любого из префиксов. А остальное - завершить логику вашей функции.

person Marius Danila    schedule 15.10.2012
comment
Благодарность! как это чаще всего бывает на SO, правильный ответ совершенно не оценен. СО сломан. его система голосования - чушь. выглядит так, как будто SO — это система курирования знаний, она представляет себя таковой, но это нет. - person Will Ness; 22.11.2020