按每个 String 的第一个 Char 对 [String] 进行分区

Question

我正在尝试编写具有以下类型的函数：

partitionByFirstChar :: [String] -> Map.Map Char [String]

partitionByFirstChar xs 将 return 一个 Map 其键是列表中每个字符串的第一个字符 xs 其值是后缀列表（即这些字符串的除第一个字符外的所有字符。

我的尝试如下：

partitionByFirstChar [] = Map.empty
partitionByFirstChar ((x:xs):xss)
  = ???
    where partitioned = partitionByFirstChar xss
          suffixes = partitioned !? x

现在 suffixes 可以是 Nothing 或 Just s。如果是Nothing，我要insert x [xs] partitioned。如果是Just s，那我要insert x (xs:s) partitioned.

我很难弄清楚如何检查 suffixes 是什么。我想我需要对 ??? 进行某种模式匹配，但不太明白。

Answer 1

如果你愿意使用 multimap 包，它很容易解决这个问题。

λ> import qualified Data.MultiMap as MM

λ> MM.toMap . MM.fromList . fmap (\(x:xs) -> (x, xs)) $ ["apple", "avocado", "bagel"]
fromList [('a',["pple","vocado"]),('b',["agel"])]

fromListWith，正如@Alec 的评论所指出的，如果您不需要使用 MultiMap 类型，可能是更好的选择。虽然性能可能不是很好，但由于列表连接。

λ> import qualified Data.Map as M

λ> M.fromListWith (<>) . fmap (\(x:xs) -> (x, [xs])) $ ["apple", "avocado", "bagel"]
fromList [('a',["vocado","pple"]),('b',["agel"])]

Answer 2

Now suffixes can be either Nothing or Just s. If it is Nothing, I want to insert x [xs] partitioned. If it is Just s, then I want to insert x (xs:s) partitioned.

这里的基本方法是使用 case of:

partitionByFirstChar [] = Map.empty
partitionByFirstChar ((x:xs):xss) = let
   partitioned = partitionByFirstChar xss
   suffixes = partitioned !? x
   in case suffixes of
      Nothing -> insert x [xs] partitioned
      Just s -> insert x (xs:s) partitioned

上面的代码仍然缺少空字符串的分支，例如：

partitionByFirstChar ("":xss) = partitionByFirstChar xss

按每个 String 的第一个 Char 对 [String] 进行分区

Partition `[String]` by the first `Char` of each `String`

string

haskell

partitioning