什麼是這種上下文無關的語言枚舉器的僞代碼實現？在Haskell中，

Question

This blog post解釋瞭如何藉助名爲Omega的monad枚舉上下文無關文法。

我不明白這是如何工作的，部分原因是缺乏關於單子如何工作的解釋，但主要是由於我無法理解單子。什麼是該算法的合適的僞代碼解釋，沒有monads？

使用類似於簡單通用語言（如JavaScript或Python）的語法將是首選。

Answer 1

這裏是一個沒有monad的Haskell版本。我確實使用列表解析，但這些 更直觀，你也可以使用它們。

Omega類型僅僅是圍繞[]的包裝，但它有助於將「符號串」和「可能的字符串列表」概念分開。由於我們不打算使用Omega爲「可能的字符串列表」，讓我們使用newtype包裝器「的符號串」把一切都直：

import Prelude hiding (String) 

-- represent a sequence of symbols of type `a`, 
-- i.e. a string recognised by a grammar over `a` 
newtype String a = String [a] 
    deriving Show 

-- simple wrapper for (++) to also make things more explicit when we use it 
joinStrings (String a1) (String a2) = String (a1 ++ a2) 

下面是從博客帖子的Symbol類型：

data Symbol a 
    = Terminal a 
    | Nonterminal [[Symbol a]] -- a disjunction of juxtapositions 

的Omega單子的核心實際上是diagonal功能：

-- | This is the hinge algorithm of the Omega monad, 
-- exposed because it can be useful on its own. Joins 
-- a list of lists with the property that for every x y 
-- there is an n such that @xs !! x !! y == diagonal xs !! n@. 
diagonal :: [[a]] -> [a] 

鑑於此，enumerate從博客帖子是：

enumerate :: Symbol a -> Omega [a] 
enumerate (Terminal a) = return [a] 
enumerate (Nonterminal alts) = do 
    alt <- each alts   -- for each alternative 
     -- (each is the Omega constructor :: [a] -> Omega a) 
    rep <- mapM enumerate alt -- enumerate each symbol in the sequence 
    return $ concat rep  -- and concatenate the results 

我們enumerate都會有這樣的類型：

enumerate :: Symbol a -> [String a] 

的Terminal情況很簡單：

enumerate (Terminal a) = [String [a]] 

在Nonterminal情況下幫手功能爲每個替代將 是有用的：

-- Enumerate the strings accepted by a sequence of symbols 
enumerateSymbols :: [Symbol a] -> [String a] 

基礎案例是很容易的，但結果不是[]，但 包含空字符串一個單結果：

enumerateSymbols [] = [String []] 

對於非空的情況下另一個輔助將是有用對了 從頭部和尾部以所有可能的方式串， 使用diagonal：

crossProduct :: [a] -> [b] -> [(a, b)] 
crossProduct as bs = diagonal [[(a, b) | b <- bs] | a <- as] 

我也可以甲肝e寫​​但 我選擇了另一個，因爲這最終複製了從 博客的輸出。

現在我們可以寫enumerateSymbols非空的情況下：

enumerateSymbols (sym:syms) = 
    let prefixes = enumerate sym 
     suffixes = enumerateSymbols syms 
    in [joinStrings prefix suffix 
      | (prefix, suffix) <- crossProduct prefixes suffixes] 

現在對於enumerate非空的情況下：

enumerate (Nonterminal alts) = 
    -- get the list of strings for each of the alternatives 
    let choices = map enumerateSymbols alts 
    -- and use diagonal to combine them in a "fair" way 
    in diagonal choices 

這裏是diagonal的身體歐米茄來源，用我的 解釋：

diagonal = diagonal' 0 
    where 

    -- strip n xss returns two lists, 
    -- the first containing the head of each of the first n lists in xss, 
    -- the second containing the tail of the first n lists in xss 
    -- and all of the remaining lists in xss. 
    -- empty lists in xss are ignored 
    stripe 0 xss   = ([],xss) 
    stripe n []   = ([],[]) 
    stripe n ([]:xss)  = stripe n xss 
    stripe n ((x:xs):xss) = 
     let (nstripe, nlists) = stripe (n-1) xss 
     in (x:nstripe, xs:nlists) 


    -- diagonal' n xss uses stripe n to split up 
    -- xss into a chunk of n elements representing the 
    -- nth diagonal of the original input, and the rest 
    -- of the original input for a recursive call to 
    -- diagonal' (n+1) 

    diagonal' _ [] = [] 
    diagonal' n xss = 
     let (str, xss') = stripe n xss 
     in str ++ diagonal' (n+1) xss' 

關於無限結構的對角化和廣度優先搜索的一般概念，還應該閱讀this paper。