Haskell-使用文件夹为函数`all`创建函数定义 [英] Haskell - creating a function definition for the function `all` using foldr

问题描述

我正在尝试使用 folder 为函数 all 创建函数定义. p 是谓词.我知道这可以做到:

I'm trying to create a function definition for the function all using foldr. p is the predicate. I know this can be done:

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

但是我要做的是将函数和转移到 folder 等式中.能做到吗?

But what I want to do is to shift the function and into the foldr equation. Can this be done?

我尝试了以下所有方法，但均无法正常工作:

I've tried the following, which all failed to work:

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

我对如何应用 folder 的理解不够吗?

Am I falling short in my understanding of how to apply foldr?

推荐答案

我们有

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 替换为(&&)立即修改:

because folding replaces each constructor with the specified combination operation (aka reducer), and replacing a cons of an element with a cons of a modified element, and then replacing that cons with (&&), is just replacing a cons of an element with the (&&) of a modified element right away:

    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

换句话说，折叠是通过融合其reduce函数来组成的，而reduce函数是通过用折叠链中的下一个fold的reduce替换{他们使用的构造函数}来融合的，从而使它们相应的 transducers 撰写(如Clojure的换能器中一样)；因此，

In other words, folds compose by fusing their reducer functions, and reducer functions fuse by replacing the {constructors they use} with the next fold's reducer in the chain of folds, so that their corresponding transducers compose (as in Clojure's transducers); thus,

 = 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)

这篇关于Haskell-使用文件夹为函数`all`创建函数定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！