與發電機

Question

的任意數的Haskell列表綜合所以我到目前爲止是這樣的：

combs :: [[Char]] 
combs = [[i] ++ [j] ++ [k] ++ [l] | i <- x, j <- x, k <- x, l <- x] 
    where x = "abc" 

因此，這是對於n = 4的工作職能，有沒有什麼辦法，使這項工作爲任意數量的發電機？我可以爲n = 1,2,3等編程，但理想情況下需要它爲任何給定的n工作。作爲參考，x只是一個任意字符串的唯一字符。我正在努力想辦法以某種方式將它解壓爲n個生成器。

Answer 1

您可以使用replicateM：

replicateM :: Applicative m => Int -> m a -> m [a] 

例如爲：

generate :: Num a => Int -> [[a]] 
generate = flip replicateM [1,2,3] 

產生給定長度的所有possiible列表和由元件1..3的。

Answer 2

據我所知，你不能用任意數量的生成器構造列表理解，但通常如果你做任意深度的事情，遞歸就是這樣做的方法。

所以我們必須考慮解決這個問題，就其本身而言。如果您想要使用x中的字符生成所有可能的字符串。在n = 0的情況下，我們可以生成一個字符串：空字符串。

combs 0 = [""] 

所以一個元素列表[]。

現在的情況下，我們要生成一個字符的字符串，我們當然可以簡單地返回x：

combs 1 = x 

現在的問題是如何處理的情況下，n > 1做。在這種情況下，我們可以獲得所有長度爲n-1的字符串，並且對於每個這樣的字符串以及每個這樣的字符在x中產生一個新的字符串。像：

combs n = [ (c:cs) | c <- x, cs <- combs (n-1) ] 

請注意，這使得第二種情況（n = 1）是多餘的。我們可以從x中挑選一個字符c，並將其預先添加到空字符串中。所以一個基本的實現是：

combs :: Int -> [[Char]] 
combs 0 = [""] 
combs n = [(c:cs) | c <- x, cs <- combs (n-1)] 
    where x = "abc" 

現在我們仍然可以尋找改進。列表理解基本上是列表monad的語法糖。因此，我們可以在這裏使用liftA2：

import Control.Applicative(liftA2) 

combs :: Int -> [[Char]] 
combs 0 = [""] 
combs n = liftA2 (:) x (combs (n-1)) 
    where x = "abc"

我們可能也想使字符集的參數：

import Control.Applicative(liftA2) 

combs :: [Char] -> Int -> [[Char]] 
combs _ 0 = [""] 
combs x n = liftA2 (:) x (combs (n-1))

，我們沒有給我們限制字符，我們可以生產出certesian功率所有可能的類型：

import Control.Applicative(liftA2) 

combs :: [a] -> Int -> [[a]] 
combs _ 0 = [[]] 
combs x n = liftA2 (:) x (combs (n-1))

Answer 3

首先，我會將理解翻譯爲單調錶達式。

x >>= \i -> x >>= \j -> x >>= \k -> x >>= \l -> return [i,j,k,l] 

隨着n = 4我們看到我們有4 x的，一般都會有nx的。因此，我在考慮長度爲n的x的列表。

[x,x,x,x] :: [[a]] 

我們該如何從[x,x,x,x]轉到monadic表達式？第一個好的猜測是foldr，因爲我們想要對列表中的每個元素進行一些操作。特別是，我們希望從每個x中獲取一個元素並用這些元素形成一個列表。

foldr :: (a -> b -> b) -> b -> [a] -> b 
-- Or more accurately for our scenario: 
foldr :: ([a] -> [[a]] -> [[a]]) -> [[a]] -> [[a]] -> [[a]] 

有兩個方面拿出了foldr相似，我會打電話f :: [a] -> [[a]] -> [[a]]和z :: [[a]]。我們知道什麼是foldr f z [x,x,x,x]：

foldr f z [x,x,x,x] = f x (f x (f x (f x z))) 

如果加上括號前面的一元表達，我們有這樣的：

x >>= \i -> (x >>= \j -> (x >>= \k -> (x >>= \l -> return [i,j,k,l]))) 

你可以看到兩個表達式是如何尋找相似。我們應該能夠找到一個f和z使它們相同。如果我們選擇f = \x a -> x >>= \x' -> a >>= \a' -> return (x' : a')我們得到：

f x (f x (f x (f x z))) 
= (\x a -> a >>= \a' -> x >>= \x' -> return (x' : a')) x (f x (f x (f x z))) 
= f x (f x (f x z)) >>= \a' -> x >>= \x' -> return (x' : a') 
= f x (f x (f x z)) >>= \a' -> x >>= \l -> return (l : a') 
= (f x (f x z) >>= \a' -> x >>= \k -> return (k : a')) >>= \a' -> x >>= \l -> return (l : a') 
= f x (f x z) >>= \a' -> x >>= \k -> x >>= \l -> return (l : k : a') 

• 請注意，我已經逆轉i,j,k,l順序l,k,j,i但在尋找組合的情況下，這應該是不相關的。如果真的擔心，我們可以試試a' ++ [x']。

的最後一步是因爲(a >>= \b -> c) >>= \d -> e相同a >>= \b -> c >>= \d -> e（佔可變衛生時）和return a >>= \b -> c相同(\b -> c) a。

如果我們繼續展開這個表達式，最終我們將在前面達到z >>= \a' -> …。這裏唯一有意義的選擇是z = [[]]。這意味着foldr f z [] = [[]]可能並不理想（改爲[]）。相反，我們可能使用foldr1（對於非空列表，我們可能使用Data.NonEmpty），或者我們可能會爲空列表添加一個單獨的子句到combs。

看着f = \x a -> x >>= \x' -> a >>= \a' -> return (x' : a')我們可能會意識到這種有用的等價性：a >>= \b -> return (c b) = c <$> a。因此，f = \x a -> x >>= \x' -> (x' :) <$> a。然後還有a >>= \b -> c (g b) = g <$> a >>= \b -> c等f = (:) <$> x >>= \x' -> x' <$> a。最後，a <*> b = a >>= \x -> x <$> b等等f = (:) <$> x <*> a。

The official implementationsequenceA列表是foldr (\x a -> (:) <$> x <*> a) (pure [])，正是我們在這裏想到的。這可以進一步縮短爲foldr (liftA2 (:)) (pure [])，但可能存在一些優化差異，使得實現者不選擇此選項。

最後一步是僅僅想出一個nx的列表。這只是replicatereplicate n x。碰巧有一個既有複製又有排序的功能，叫做replicateMreplicateM n x。