Haskell - создание определения функции для функции `all` с помощью foldr - PullRequest
Новая
       37

Haskell - создание определения функции для функции `all` с помощью foldr

0 голосов
/ 11 июля 2020

Я пытаюсь создать определение функции для функции all, используя foldr. p - это предикат. Я знаю, что это можно сделать: 

all p = and . foldr (\x xs -> p x : xs) []

Но я хочу сдвинуть функцию and в уравнение foldr. Можно ли это сделать?

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

all p = foldr (\x p -> \ys -> and (p x) ys) True
all p = foldr (\x and -> (\ys -> (p x and ys))) True
all p = foldr (\x ys -> and . (p x) ys) True

Я не понимаю, как применять foldr?

1 Ответ

5 голосов
/ 11 июля 2020

У нас есть 

all p = and 
         . foldr (\x xs -> p x :  xs) []    
      = foldr                 (&&)   True   -- {y : ys} -> y && {ys}      2-3
         . foldr (\x xs -> p x :  xs) []    -- {x , xs} -> p x : {xs}   1-2
      =    foldr (\x xs -> p x && xs) True  -- {x , xs} -> p x && {xs}  1---3

, потому что сворачивание заменяет каждый конструктор указанной комбинированной операцией (также известной как reducer ) и заменяет cons элемента на cons измененного элемента, а затем замена этого cons на (&&), просто заменяет cons элемента на (&&) измененного element сразу: 

    a  : (  b  : (  c  : (  d  : ( ... ))))   _OR_   []      --   |       |   1
                                                             --   |       |
  p a  : (p b  : (p c  : (p d  : ( ... ))))   _OR_   []      --   ↓   |   |   2
                                                             --       |   |
  p a && (p b && (p c && (p d && ( ... ))))   _OR_  True     --       ↓   ↓   3

Другими словами, свертки объединяются путем объединения своих функций-редукторов, а функции-редукторы объединяются, заменяя {конструкторы, которые они используют} редуктором следующей свертки в цепочке складок, так что их соответствующие преобразователи составляют (как в преобразователях Clojure); таким образом, 

 = foldr              (reducingWith (&&)) True
     . foldr ((mapping p)    (:))           []
 = foldr ((mapping p) (reducingWith (&&))) True
 = foldr ((mapping p . reducingWith) (&&) ) True
   -- first map p, then reduce with (&&)

для соответствующих определений reducingWith и mapping: 

reducingWith cons x xs = cons x xs
mapping f cons x xs = cons (f x) xs
filtering p cons x xs | p x = cons x xs
                      | otherwise = xs
concatting t cons x xs = foldr cons xs (t x)
...