时间戳

首页 > 解决方案 > 如何根据第一个值生成元组列表的笛卡尔连接？

haskell - 如何根据第一个值生成元组列表的笛卡尔连接？

问题描述

我有一个类型的元组列表，(Int,String)我想生成一个类型列表，[String]其中每个字符串都是具有相同Int值的元组的第二个元素的笛卡尔连接排列。例如：

输入：[(1,"abc"),(1,"def"),(2,"ghi"),(2,"kl")]

输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf", "gk", "gl", "hk", "hl", "ik", "il"]

我试过这个，但我找不到一种方法来排列具有相同Int值的元组：

possible_keys :: [(Int,String)] -> [String]
possible_keys subkeys = [ key | keysize <- keysizes, key<-keys]
  where keysizes = map (fst) subkeys
        keys = sequence (map (snd) subkeys)

有什么提示吗？

标签： haskell

解决方案

您可以使用groupBy将元组组分开：

import Data.Function (on)
import Data.Ord (comparing)
import Data.List

possible_keys :: Ord k => [(k, [c])] -> [[c]]
possible_keys = concat . fmap sequenceA . fmap (fmap snd)
    . groupBy ((==) `on` fst) . sortBy (comparing fst)

（我假设输入列表不一定是排序的。我只按键排序以使其侵入性最小。comparing fst与 相同；不幸的是，标准库中还compare `on` fst没有类似的。与，只是更一般。）equatingsequenceAsequence

这可以瘦一点。第二函子定律允许我们结合 的连续使用fmap：

possible_keys :: Ord k => [(k, [c])] -> [[c]]
possible_keys = concat . fmap (sequenceA . fmap snd)
    . groupBy ((==) `on` fst) . sortBy (comparing fst)

fmap其次sequenceA是traverse：

possible_keys :: Ord k => [(k, [c])] -> [[c]]
possible_keys = concat . fmap (traverse snd)
    . groupBy ((==) `on` fst) . sortBy (comparing fst)

最后，在一个列表fmap后面是（或，但这在这里有点太神秘了）：concatconcatMap(=<<)

possible_keys :: Ord k => [(k, [c])] -> [[c]]
possible_keys = concatMap (traverse snd)
    . groupBy ((==) `on` fst) . sortBy (comparing fst)

请注意，这将为只有一个元组的键生成长度为 1 的字符串 - sequenceA ["abc"]is ["a","b","c"]。如果你不想这样，你可以filter在之后立即groupBy删除那些只有一个元组的元组组。

推荐阅读