Функция фильтра в решателе неграмм - PullRequest
Новая
       43

Функция фильтра в решателе неграмм

0 голосов
/ 22 мая 2019

Я должен понять дедуктивный решатель Тед Инь из https://wiki.haskell.org/Nonogram

Я не знаю, как работает 

elim b w ps = filter (\p -> all (\x -> x `elem` p) b &&
                            all (\x -> x `notElem` p) w) ps

.Я только знаю, что 

all (\x -> x `notElem` [1]) [1,2,3,4]

дает False, а 

all (\x -> x `elem` [1]) [1,1,1,1]

дает True.

, но я не знаю, как запустить все elim функция и как она работает

1 Ответ

3 голосов
/ 22 мая 2019

Во-первых, найдите себе пробел для понимания и назовите свои подвыражения: 

elim b w ps = filter (\p -> all (\x -> x `elem`    p) b  &&
                            all (\x -> x `notElem` p) w
                       ) ps

            = filter foo ps
                where
                   foo p =  all (\x -> x `elem`    p) b  &&
                            all (\x -> x `notElem` p) w

            = filter foo ps
                where
                   foo p =  all tst1 b  &&  all tst2 w
                      where
                         tst1 = (\x -> x `elem`    p)
                         tst2 = (\x -> x `notElem` p)

            = filter foo ps
                where
                   foo p =  (&&)  (all tst1 b)  (all tst2 w)
                      where
                         tst1 x = elem    x p
                         tst2 y = notElem y p

Теперь, что это делает? Или еще лучше, что это? Давайте рассмотрим некоторые типы, чтобы создать наше понимание здесь: 

filter :: (a ->                Bool) -> [a] -> [a]
foo    ::  a ->                Bool
ps     ::                               [a]
filter    foo                           ps  :: [a]
p      ::  a
foo        p                :: Bool
(&&)        :: Bool -> Bool -> Bool
all tst1 b  :: Bool
all tst2 w  ::         Bool
---------------------------
all  :: (t -> Bool) -> [t] -> Bool
tst1 ::  t -> Bool
tst2 ::  t -> Bool
b    ::                [t]
w    ::                [t]
---------------------------
......
---------------------------
elim             b      w               ps  :: [a]
elim ::         [t] -> [t] ->           [a] -> [a]

Завершите картину, работая с типами tst1 и tst2, чтобы выяснить взаимосвязь между типами t и a. 

tst1    ::         t        -> Bool          -- tst1 x = elem    x p
tst2    ::         t        -> Bool          -- tst2 y = notElem y p
x       ::         t
y       ::         t
elem    :: Eq t => t -> [t] -> Bool
notElem :: Eq t => t -> [t] -> Bool
p       ::              [t]                  -- it was : a !

Таким образом a ~ [t] и [a] ~ [[t]] и, наконец, 

elim             b      w               ps  :: [[t]]
elim :: Eq t => [t] -> [t] ->         [[t]] -> [[t]]

Итак, filter foo оставляет только те p s в ps, для которых foo p == True.

А это значит all tst1 b == True и all tst2 w == True.

И это означает, что каждый x в b является элементом p, а каждый y в w является , а не элементом в p. Или, другими словами, только такие p s в ps оставлены одни в результирующем списке, для которого 

foo p =  (b \\ p) == []   &&   (p \\ w) == p

имеет место: 

import Data.List (\\)

elim b w ps = [ p | p <- ps, (b \\ p) == [], (p \\ w) == p ]
...