使用对 foldmap 的调用在 Haskell 中的频率分布

Question

我对 Haskell 很陌生。我可以用什么来替换下面定义中的“未定义”，以便“频率” 计算输入列表中项目的频率分布。例如，表达式“频率 [True, False, True]”应该产生一个分布其中 True 的频率为 2，False 的频率为 1。

我可以添加新的顶级函数定义，但不能修改任何其他 “频率”定义的一部分。特别是，我不能添加任何附加命名参数或在定义中删除对“foldMap”的调用 “频率”。

type Dist a = a -> Sum

frequencies :: Eq a => [a] -> Dist a
 frequencies = foldmap = undefined

Answer 1

您可以通过使用 GHC typed holes 的类型来实现这一点，输入下划线 _ 以询问编译器应该是什么类型的表达式。

import Data.Semigroup (Sum(..))

-- Using the standard 'Sum' for illustration.
type Dist a = a -> Sum Int

frequencies :: (Eq a) => [a] -> Dist a
frequencies = foldMap _

此处，编译器报告 _ :: a -> Dist a。所以我们在输入中给定每个 a 值，并且必须产生相应的 Dist a，然后将它们与 foldMap 组合成最终结果。这依赖于函数有 Semigroup 和 Monoid 个实例，它们只是组合它们的结果：

instance (Semigroup m) => Semigroup (a -> m) where
  f <> g = \ x -> f x <> g x

instance (Monoid m) => Monoid (a -> m) where
  mempty = \ _x -> mempty

Dist a 是一个函数，它接受一个 a 和 returns 一个 Sum，可以使用它的 Semigroup/[=25= 组合起来] 实例来添加结果。所以我们要引入一个lambda：

frequencies :: (Eq a) => [a] -> Dist a
frequencies = foldMap (\ x -> _)

这个洞现在的类型是Dist a，这是一个函数，所以我们引入另一个参数：

frequencies :: (Eq a) => [a] -> Dist a
frequencies = foldMap (\ x -> \ y -> _)

现在我们必须生成一个 Sum Int 值。我们只有两个 a 值，以及一个 a 可以与 Eq 进行比较的约束。所以让我们引入一个if来测试它们是否相等：

frequencies :: (Eq a) => [a] -> Dist a
frequencies = foldMap (\ x -> \ y -> if x == y then _ else _)

我们应该为孔使用什么 Sum 值？据推测，如果值相等，我们想在总数上加 1，如果它们不同，则什么也不加。所以我们可以使用 Sum 1 表示真实情况，mempty（或 Sum 0）表示错误情况。我们还可以使用多个参数的普通语法糖来折叠 lambda。

frequencies :: (Eq a) => [a] -> Dist a
frequencies = foldMap (\ x y -> if x == y then Sum 1 else mempty)

现在我们可以在列表上调用这个函数，它会生成一个函数，为我们提供特定元素的频率。

> f = frequencies "AAB"
> :t f
f :: Dist Char
> f 'A'
Sum {getSum = 2}
> f 'B'
Sum {getSum = 1}

由此，我们可以构建更多有趣的东西，比如直方图：

import Data.List (nub)

histogram :: (Ord a) => [a] -> [(a, Int)]
histogram xs = let
  keys = nub (sort xs)
  frequency = frequencies xs
  in zip keys (map (getSum . frequency) keys)

> histogram "AAB"
[('A',2),('B',1)]

使用对 foldmap 的调用在 Haskell 中的频率分布

Dist of a Frequency in Haskell using a call to foldmap

haskell

distribution

frequency