在Haskell中使用HoF实现过滤器

Question

我正在尝试编写一个函数,该函数接受谓词f和列表,并返回一个列表,该列表包含满足保留顺序的f的所有项.诀窍是只使用更高阶函数(HoF),没有递归,没有理解,当然也没有过滤器.

Answer 1

你可以表达filter在以下方面foldr:

filter p = foldr (\x xs-> if p x then x:xs else xs) []

Answer 2

我想你可以用map这种方式:

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = concat (map (\x -> if (p x) then [x] else []) xs)

你看？转换列表列表中的列表,如果所需的元素未传递p,则转为空列表

filter' (> 1) [1 , 2, 3 ] 将会: concat [ [], [2], [3]] = [2,3]

在前奏中concatMap,使代码更简单:P

代码应如下所示:

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = concatMap (\x -> if (p x) then [x] else []) xs

使用foldr,如sclv所建议的,可以使用以下内容完成:

filter'' :: (a -> Bool) -> [a] -> [a]
filter'' p xs = foldr (\x y -> if p x then (x:y) else y) [] xs

Answer 3

你很明显这是为了学习,所以让我向你展示一些很酷的东西.首先,为了刷新我们的想法,过滤器的类型是:

filter :: (a -> Bool) -> [a] -> [a]

最有趣的部分是最后一点[a] -> [a].它打破了一个列表,并建立了一个新列表.

递归模式在Haskell(和其他函数语言)中非常常见,人们已经为这些模式中的某些模式提出了名称.最简单的是变形,它是变形的双重性.我会告诉你这与你最近的问题有何关系.

固定点

必备知识FTW!

是什么类型的Nothing？解雇GHCI,它说Nothing :: Maybe a,我不会不同意.怎么样Just Nothing？再次使用GHCI,它说Just Nothing :: Maybe (Maybe a)哪个也是完全有效的,但是这个Nothing嵌入任意数字,甚至是无限数量的Justs的值.即,这个值的类型是什么:

foo = Just foo

Haskell实际上并没有允许这样的定义,但稍微调整一下我们可以做出这样的类型:

data Fix a = In { out :: a (Fix a) }

just :: Fix Maybe -> Fix Maybe
just = In . Just

nothing :: Fix Maybe
nothing = In Nothing

foo :: Fix Maybe
foo = just foo

哇,足够近!使用相同的类型,我们可以创建任意嵌套的nothings:

bar :: Fix Maybe
bar = just (just (just (just nothing)))

旁白:Peano算术有人吗？

fromInt :: Int -> Fix Maybe
fromInt 0 = nothing
fromInt n = just $ fromInt (n - 1)

toInt :: Fix Maybe -> Int
toInt (In Nothing) = 0
toInt (In (Just x)) = 1 + toInt x

这种Fix Maybe类型有点无聊.这是一个固定点是列表的类型:

data L a r = Nil | Cons a r
type List a = Fix (L a)

这种数据类型将有助于演示一些递归模式.

实用信息:rin Cons a r称为递归站点

Catamorphism

catamorphism是一种破坏结构的操作.列表的catamorphism更好地称为折叠.现在,变形的类型可以这样表达:

cata :: (T a -> a) -> Fix T -> a

哪个可以等效地写成:

cata :: (T a -> a) -> (Fix T -> a)

或者用英语:

你给我一个函数,将数据类型减少到一个值,我会给你一个函数,将它的固定点减少到一个值.

实际上,我撒了谎,这种类型真的是:

cata :: Functor T => (T a -> a) -> Fix T -> a

但原则是一样的.注意,T仅对递归网站的类型进行参数化,因此该Functor部分实际上是在说"给我一种操纵所有递归网站的方法".

然后cata可以定义为:

cata f = f . fmap (cata f) . out

这是非常密集的,让我详细说明.这是一个三步过程:

• 首先,我们给了一个Fix t,这是一个很难玩的类型,我们可以通过应用out(从定义Fix)给我们一个更容易t (Fix t).
• 接下来我们要转换t (Fix t)成一个t a,这是我们可以做的,通过一厢情愿,使用fmap (cata f); 我们假设我们能够建造cata.
• 最后,我们有一个t a,我们想要一个a,所以我们只是使用f.

之前我说过列表的变形被称为折叠,但cata目前看起来并不像折叠.让我们根据方式定义折叠函数cata.

重新封装,列表类型为:

data L a r = Nil | Cons a r
type List a = Fix (L a)

这需要是一个有用的算子,这是直截了当的:

instance Functor (L a) where
  fmap _ Nil = Nil
  fmap f (Cons a r) = Cons a (f r)

所以cata我们专业化:

cata :: (L x a -> a) -> List x -> a

我们几乎在那里:

construct :: (a -> b -> b) -> b -> L a b -> b
construct _ x (In Nil) = x
construct f _ (In (Cons e n)) = f e n

fold :: (a -> b -> b) -> b -> List a -> b
fold f m = cata (construct f m)

好吧,catamorphisms一次打破一层数据结构.

Anamorphisms

列表上的呐喊是展开的.展开不像折叠双胞胎那么常见,它们的类型如下:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

正如您所看到的,anamorphisms构建了数据结构.这是更一般的类型:

ana :: Functor a => (a -> t a) -> a -> Fix t

这应该立即看起来很熟悉.这个定义也让人想起了这种变形.

ana f = In . fmap (ana f) . f

这是相反的事情.构建unfold起来ana比构建fold起来更简单cata.注意Maybe (a, b)和之间的结构相似性L a b.

convert :: Maybe (a, b) -> L a b
convert Nothing = Nil
convert (Just (a, b)) = Cons a b

unfold :: (b -> Maybe (a, b)) -> b -> List a
unfold f = ana (convert . f)

把理论付诸实践

过滤器是一个有趣的功能,因为它可以从一个变形或一个变形构造.这个问题的其他答案(迄今为止)也使用了catamorphisms,但我将两种方式定义:

filter p = foldr (\x xs -> if p x then x:xs else xs) []

filter p =
  unfoldr (f p)
 where
  f _ [] =
    Nothing
  f p (x:xs) =
    if p x then
      Just (x, xs)
    else
      f p xs

是的,是的,我知道我在展开版本中使用了递归定义,但请原谅我,我教会了很多理论,无论如何过滤器都不是递归的.