làm thế nào tôi có thể thực hiện biến áp đơn nguyên này với sự tiếp tục?

Question

động lực. Tôi đang cố gắng để tạo ra một biến áp đơn lẻ, với một hướng dẫn đặc biệt f <||> g có nghĩa là "lặp lại toàn bộ khối này có chứa f <||> g, một lần với f, lần sau với g". Điều này được dự định là để chuyển đổi DSL, mặc dù bạn có thể tưởng tượng các ứng dụng khác.

ví dụ về cách sử dụng. Các đơn vị computation thể hiện các lựa chọn khác nhau có thể (trong trường hợp này, những thứ cần in). Hàm printme cho biết phải làm gì với mỗi kết quả khác nhau. Trong trường hợp này, chúng tôi in "bắt đầu tính toán" trước khi nó chạy, và "---" sau.

computation = do 
    lift (print "start -- always") 
    (lift (print "first choice") <||> lift (print "second choice")) 
    lift (print "intermediate -- always") 
    (lift (print "third choice") <||> lift (print "fourth choice")) 
    lift (print "end -- always") 

printme x = do 
    putStrLn "=== start computation" 
    xv <- x 
    putStrLn "---\n" 
    return xv 

test = runIndep printme computation 

đầu ra là như sau,

=== start computation 
"start -- always" 
"first choice" 
"intermediate -- always" 
"third choice" 
"end -- always" 
--- 

=== start computation 
"start -- always" 
"first choice" 
"intermediate -- always" 
"fourth choice" 
"end -- always" 
--- 

=== start computation 
"start -- always" 
"second choice" 
"intermediate -- always" 
"third choice" 
"end -- always" 
--- 

=== start computation 
"start -- always" 
"second choice" 
"intermediate -- always" 
"fourth choice" 
"end -- always" 
--- 

câu hỏi. Có cách nào sạch sẽ để đạt được các hành vi trên bằng cách sử dụng một số loại tiếp tục đi qua biến áp kiểu đơn? Tôi đã xem xét bài báo "Backtracking, Interleaving, and Terminating Unad Transformers" của Oleg và cộng sự, nhưng dường như không thể nắm bắt đầy đủ việc thực hiện của họ (một khi họ có thể thực hiện msplit với sự tiếp tục).

triển khai hiện tại. Triển khai hiện tại của tôi là chuyển một danh sách các quyết định phân nhánh được thực hiện. Đơn nguyên sẽ trả về danh sách các nhánh mà nó thực sự chọn, và lần sau chúng ta sẽ chuyển nhánh cuối cùng có thể. Mã này là như sau (nên chạy ở 7.0.3),

import Control.Monad.Trans.Class 

data IndepModelT α = IndepModelT { 
    unIndepModelT :: [Bool] -> (α, [Bool]) } 

instance Monad => Monad (IndepModelT) where 
    return x = IndepModelT $ \choices -> return (x, []) 
    (IndepModelT x) >>= f = IndepModelT $ \choices -> do 
     (xv, branches) <- x choices 
     let choices' = drop (length branches) choices 
     (fxv, branches') <- unIndepModelT (f xv) choices' 
     return (fxv, branches ++ branches') 

instance MonadTrans IndepModelT where 
    lift x = IndepModelT $ \c -> liftWithChoice [] x 
liftWithChoice cs mx = mx >>= \xv -> return (xv, cs) 

(<||>) 
    :: Monad => IndepModelT α -> IndepModelT α -> IndepModelT α 
(IndepModelT f) <||> (IndepModelT g) = IndepModelT go where 
    go (False:cs) = do 
     (fv, branches) <- f cs 
     return (fv, False : branches) 
    go (True:cs) = do 
     (fv, branches) <- g cs 
     return (fv, True : branches) 

run_inner next_choices k comp@(IndepModelT comp_inner) = do 
    (xv, branches) <- k $ comp_inner next_choices 
    case (get_next_choices branches) of 
     Nothing -> return() 
     Just choices -> run_inner (choices ++ repeat False) k comp 
    where 
     get_next_choices [] = Nothing 
     get_next_choices [True] = Nothing 
     get_next_choices [False] = Just [True] 
     get_next_choices (c:cs) 
      | Just cs' <- get_next_choices cs = Just $ c:cs' 
      | c Prelude.== False = Just [True] 
      | otherwise = Nothing 

runIndep :: Monad => 
    ((α, [Bool]) -> (β, [Bool])) 
    -> IndepModelT α 
    -> () 
runIndep = run_inner (repeat False) 

runIndepFirst (IndepModelT comp) = comp (repeat False) 

Answer 1

Đây là vấn đề: đây không phải là một đơn nguyên! Hành vi thậm chí không được xác định rõ. F.e. những gì nó nên làm gì trong trường hợp này:

do 
    b <- ...randomly True or False... 
    if b then ...some choices... else ...some other choices... 

Tuy nhiên, nó là Applicative.Loại chúng tôi cần là [IO a], là thành phần của 2 ứng viên, vì vậy chúng tôi có thể sử dụng Data.Functor.Compose từ gói máy biến áp. Điều này cho phép một ví dụ Alternative với số <|> miễn phí. Chúng tôi sẽ sử dụng Cú pháp có thể phục hồi để sử dụng ký hiệu cho các ứng dụng:

{-# LANGUAGE RebindableSyntax #-} 
import Prelude hiding ((>>), (>>=)) 
import Control.Applicative 
import Data.Functor.Compose 

lift :: Applicative f => g a -> Compose f g a 
lift = Compose . pure 

(>>) :: Applicative f => f a -> f b -> f b 
(>>) = (*>) 

computation :: Alternative f => Compose f IO() 
computation = do 
    lift (print "start -- always") 
    lift (print "first choice") <|> lift (print "second choice") 
    lift (print "intermediate -- always") 
    lift (print "third choice") <|> lift (print "fourth choice") 
    lift (print "end -- always") 

printme x = do 
    putStrLn "=== start computation" 
    x 
    putStrLn "---\n" 

test = mapM printme $ getCompose computation 

Answer 2

Nếu bạn đang tìm cách cụ thể cho một cách tiếp cận tiếp tục dựa vào, bạn sẽ không có được đơn giản hơn nhiều so với SFKT thành công/thất bại liên tục thực hiện trong the LogicT paper.

Nếu msplit quá nhiều (và nó khá là một con thú tinh tế), bạn có thể bỏ qua nó cho ứng dụng này. Mục đích của nó là cho phép kết hợp công bằng và tách rời, mà không phải là một phần của đặc tả của bạn nếu những dòng đầu ra mẫu đó có nghĩa là in theo thứ tự. Chỉ cần tập trung vào các triển khai Monad và MonadPlus trong phần 5.1 và bạn sẽ hoàn tất.

Cập nhật: Như Sjoerd Visscher chỉ ra, điều này không đúng khi khởi động lại chỉ xảy ra từ mplus thay vì toàn bộ tính toán. Đây là một vấn đề phức tạp hơn nhiều so với lần đọc đầu tiên.

Answer 3

Đề xuất bạn đã nhận được cho đến nay không hoạt động. Đây là cách mà có thể đi:

f <||> g = ContT $ \k -> do 
    xs <- runContT f k 
    ys <- runContT g k 
    return $ xs ++ ys 

test = runContT computation (return . (:[])) 

Nhưng điều đó không khởi động lại toàn bộ tính toán cho mỗi lựa chọn, kết quả là thế này:

"start -- always" 
"first choice" 
"intermediate -- always" 
"third choice" 
"end -- always" 
"fourth choice" 
"end -- always" 
"second choice" 
"intermediate -- always" 
"third choice" 
"end -- always" 
"fourth choice" 
"end -- always" 

tôi đã không tìm thấy một giải pháp tốt được nêu ra.