Haskell中对列表列表的Foldl操作

Question

我有一个列表列表，例如

[[1,2,3,5],[24,6,8,2],[2,4,5,6,8]]

目标是获得所有列表中通用的元素列表。我的方法是创建一个函数，输出两个列表中的公共元素

common :: (Foldable t, Eq a) => [a] -> t a -> [a]
common list1 list2 = [x | x<-list1, elem x list2]

并使用折叠操作对[[a]]的所有元素递归地进行操作

main :: IO ()
main = do
--- get the number of lists
q <- readLn :: IO Int
--- get the lists and store in a list of lists
list_of_lists <- map (map (read::String->Int ) . words) <$> replicateM q getLine :: IO [[Int]]
--- process and print the output
putStrLn $ show $ foldl (common) list_of_lists

不幸的是，这没有编译，并给出错误

• Ambiguous type variable ‘t1’ arising from a use of ‘common’
prevents the constraint ‘(Foldable t1)’ from being solved.
Probable fix: use a type annotation to specify what ‘t1’ should be.
These potential instances exist:
instance Foldable (Either a) -- Defined in ‘Data.Foldable’
instance Foldable Maybe -- Defined in ‘Data.Foldable’
instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
...plus one other
...plus 26 instances involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the first argument of ‘foldl’, namely ‘(common)’
In the second argument of ‘($)’, namely ‘foldl (common) list_of_lists’
In the second argument of ‘($)’, namely
‘show $ foldl (common) list_of_lists’

我可以理解可能的解决方案在于函数common是如何定义的，但似乎无法理解，因为我对Haskell相对陌生。

Answer 1

您应该使用foldl1，或者为累加器提供初始值foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b需要一个初始值作为b类型的累加器。对于foldl1 :: Foldable t => (a -> a -> a) -> t a -> a，它将第一个元素作为初始累加器：

import Control.Monad(replicateM)
main :: IO ()
main = do
q <- readLn :: IO Int
list_of_lists <- replicateM q (map read . words <$> getLine) :: IO [[Int]]
print (foldl1common list_of_lists)

这给了我们：

Prelude Control.Monad> main
3
1 2 3 5
24 6 8 2
2 4 5 6 8
[2]

如果项目列表为空，则上述函数将出错。所以这里q应该像@JosephSible说的那样，严格地大于零。