Haskell：整數的列表組合

Question

我有一個給定的列表，例如[2, 3, 5, 587]，我想要一個完整的組合列表。所以想要像[2, 2*3,2*5, 2*587, 3, 3*5, 3*587, 5, 5*587, 587]。由於我在Haskell的初學者水平上，我很好奇列表操作是怎麼樣的。

此外，我很好奇，如果計算的基礎列表可能會很昂貴，這將如何影響功能的成本？ （如果我將承擔名單有極限值，即< 20）

雷姆：列表的順序可以事後做，但我也實在沒有線索，如果是這樣的功能或之後內便宜。

Answer 1

因此，看來你想要的是列表中的所有對產品：

ghci> :m +Data.List 
ghci> [ a * b | a:bs <- tails [2, 3, 5, 587], b <- bs ] 
[6,10,1174,15,1761,2935] 

但你也想inital號：

ghci> [ a * b | a:bs <- tails [2, 3, 5, 587], b <- 1:bs ] 
[2,6,10,1174,3,15,1761,5,2935,587] 

這將使用列表理解，但是這可能也可以通過定期列表操作完成：

ghci> concatMap (\a:bs -> a : map (a*) bs) . init $ tails [2, 3, 5, 587] 
[2,6,10,1174,3,15,1761,5,2935,587] 

後者有點容易解釋：

• Data.List.tails產生一個列表的所有後綴：

  ghci> tails [2, 3, 5, 587] 
  [[2,3,5,587],[3,5,587],[5,587],[587],[]] 
  

• Prelude.init從列表中滴的最後一個元素。在這裏，我使用它來刪除空白後綴，因爲在下一步中會導致錯誤的處理。

  ghci> init [[2,3,5,587],[3,5,587],[5,587],[587],[]] 
  [[2,3,5,587],[3,5,587],[5,587],[587]] 
  
  ghci> init $ tails [2, 3, 5, 587] 
  [[2,3,5,587],[3,5,587],[5,587],[587]] 
  

• Prelude.concatMap運行在一個列表的每個元素的功能，並且將結果組合成扁平列表。所以

  ghci> concatMap (\a -> replicate a a) [1,2,3] 
  [1, 2, 2, 3, 3, 3] 
  

• \(a:bs) -> a : map (a*) bs做了幾件事情。我的論點

  1. 我模式匹配，聲稱它的匹配列表與至少一個元素（這就是爲什麼我init放棄了空列表），配件初始元素爲a和後來的元素融入bs。
  2. 這產生了具有相同的第一元件作爲參數a:列表，但
  3. 乘以a（map (a*) bs）每個後來元件。

Answer 2

你可以使用Data.List.tails列表的後綴。 這給你一個列表的列表，那麼你可以做你想做的內乘這個名單上有類似的功能：

prodAll [] = [] 
prodAll (h:t) = h:(map (* h) $ t) 

然後，您可以映射在每個內部列表此功能並連接結果：

f :: Num a => [a] -> [a] 
f = concat . map prodAll . tails 

Answer 3

其他人解釋瞭如何做對，所以我在這裏關心自己與獲得的組合。

如果你想的所有長度的組合，這只是你的名單power set，並且可以計算方式如下：

powerset :: [a] -> [[a]] 
powerset (x:xs) = let xs' = powerset xs in xs' ++ map (x:) xs' 
powerset []  = [[]] 

-- powerset [1, 2] === [[],[2],[1],[1,2]] 
-- you can take the products: 
-- map product $ powerset [1, 2] == [1, 2, 1, 2] 

有哈斯克爾替代powerset實現人們心目中的排序的經典：

import Control.Monad 

powerset = filterM (const [True, False]) 

你可以看看filterM的source，看看它是如何工作本質上是相同的方式爲行吟詩人以上爲powerset。

在另一方面，如果你想有一定規模的所有組合，你可以做到以下幾點：

combsOf :: Int -> [a] -> [[a]] 
combsOf n _ | n < 1 = [[]] 
combsOf n (x:xs) = combsOf n xs ++ map (x:) (combsOf (n - 1) xs) 
combsOf _ _   = [] 

-- combsOf 2 [1, 2, 3] === [[2,3],[1,3],[1,2]]