2017-05-29 104 views
3

我想創建一些代碼,可以採取任何遞歸語法數據類型和該數據類型的任何表達式,併產生一個相同類型的所有子表達式的列表,建立起來的,種類就像一個scan這個類型的遞歸。遞歸類型Lensing

我已經爲伴隨的玩具計算器語法類型EExp編寫了兩個手動示例。第一個示例使用Lens庫中的棱鏡和透鏡,僅適用於一個eg1示例表達式,而第二個函數僅使用手動代碼,但可用於任何EExp表達式。

理想情況下,我可以使用模板哈希克爾或其他東西來自動構建一個遞歸函數,可以集中在該類型的任何類型的表達式的每個子表達式(如棱鏡/鏡頭),因此也可以輕鬆地打印列出所有賦予它的表達式的列表。

但是,我有點卡住了,接下來要嘗試或研究什麼。任何幫助真的很感激!

import qualified Control.Lens as Lens 
import qualified Control.Lens.TH as LTH 


-- Syntax for toy language 

data EExp a 
    = ELit a 
    | EAdd (EExp a) (EExp a) 
    | EMul (EExp a) (EExp a) 
    | ESub (EExp a) (EExp a) 
    deriving Show 

-- build out a set of focus functions using lens/TH 

LTH.makePrisms ''EExp 


-- An example "text" in the Syntax 

eg1 :: EExp Int 
eg1 = EAdd 
     (ELit 1) 
     (EAdd (ELit 2) (ELit 0)) 

-- using lenses, we build out all the 
-- EExp possibilities from the example "text": 

lensedOptions :: Show a => EExp a -> [EExp a] 
lensedOptions exp = 
    let 
    maybeGet l = Lens.preview l exp 
    listMaybes = 
     [ Just exp 
     , maybeGet (_EAdd.(Lens._1)) 
     , maybeGet (_EAdd.(Lens._2)) 
     , maybeGet (_EAdd.(Lens._2)._EAdd.(Lens._1)) 
     , maybeGet (_EAdd.(Lens._2)._EAdd.(Lens._2)) 
     ] 
    in 
    maybe [] id $ sequenceA listMaybes 

printEm :: IO() 
printEm = sequence_ $ map print $ lensedOptions eg1 

-- using handwritten code, we build out all the 
-- EExp possibilities from the example "text": 


buildOptions :: Show a => EExp a -> [EExp a] 
buildOptions exp = 
    let 
    buildBinOpts e1 e2 = [exp] ++ buildOptions e1 ++ buildOptions e2 
    in 
    case exp of 
     ELit i -> [exp] 
     EAdd e1 e2 -> 
     buildBinOpts e1 e2 
     EMul e1 e2 -> 
     buildBinOpts e1 e2 
     ESub e1 e2 -> 
     buildBinOpts e1 e2 

printEm2 :: IO() 
printEm2 = sequence_ $ map print $ buildOptions eg1 

回答

3

您正在尋找Control.Lens.Plated模塊。

加上一個Data推導:

{-# language DeriveDataTypeable #-} 
import Data.Data 
import Data.Data.Lens 
import Control.Lens -- for universeOf function 

data EExp a 
    = ELit a 
    | EAdd (EExp a) (EExp a) 
    deriving (Show, Data) 

然後:

> buildOptions eg1 
[EAdd (ELit 1) (EAdd (ELit 2) (ELit 0)),ELit 1,EAdd (ELit 2) (ELit 0),ELit 2,ELit 0] 

> universeOf uniplate eg1 
[EAdd (ELit 1) (EAdd (ELit 2) (ELit 0)),ELit 1,EAdd (ELit 2) (ELit 0),ELit 2,ELit 0] 

uniplate鏡頭是做大頭這裏的神奇;使用Data typeclass提供的信息,它能夠步入任何Data-友好的數據結構以找到自相似的孩子。它也在做some high-altitude caching gymnastics以使遍歷有效,但我們可以放心地忽略它。

universeOf uniplate反覆調用uniplate找到所有傳遞後代。

欲瞭解更多關於Data.Data的信息,請查看Lämmel和SPJ的Scrap Your Boilerplate paper

+0

太棒了! <3非常感謝@haoformayor。我一定會很快閱讀這篇文章(當我最初考慮Haskell中的泛型編程時,出於興趣,我想我已經嘗試了幾次,但它比其他任何東西都更加粗糙感興趣)。 –

+0

根據我的GHC,擴展實際上被稱爲'DeriveDataTypeable'。我會糾正你寫的。 –

+0

此外,我無法獲得您編寫的代碼工作。你回答之前是否嘗試過編譯它?我想我過早地接受了你的回答,因爲我應該先自己嘗試。現在只有這樣。我想知道你可能是不是說'universeOf'?我需要更多地研究這個。 –