Có cách nào thanh lịch để có chức năng trả về cùng loại (trong một bộ)

Question

Tôi đang sử dụng haskell để triển khai mẫu liên quan đến các hàm trả về một giá trị và chính chúng (hoặc một hàm cùng loại). Ngay bây giờ tôi đã thực hiện điều này như sau:

newtype R a = R (a , a -> R a) 

-- some toy functions to demonstrate  
alpha :: String -> R String 
alpha str 
    | str == reverse str = R (str , omega) 
    | otherwise   = R (reverse str , alpha) 

omega :: String -> R String 
omega (s:t:r) 
    | s == t = R (s:t:r , alpha) 
    | otherwise = R (s:s:t:r , omega) 

Các động lực thúc đẩy cho các loại chức năng là một chức năng gọi là thác:

cascade :: (a -> R a) -> [a] -> [a] 
cascade _ [] = [] 
cascade f (l:ls) = el : cascade g ls where 
    R (el , g) = f l 

nào mất một chức năng giống và một danh sách, và trả về một danh sách được tạo ra bằng cách áp dụng hàm hạt giống cho phần tử đầu tiên của danh sách, áp dụng hàm trả về cho phần tử thứ hai của danh sách, và cứ tiếp tục như vậy.

Công trình này - tuy nhiên, trong quá trình sử dụng điều này cho những thứ hữu ích hơn một chút, tôi nhận thấy rằng rất nhiều lần tôi có các đơn vị cơ bản trong số đó là các chức năng trả về các chức năng khác ngoài bản thân chúng hiếm khi; và tuyên bố rõ ràng một hàm để trả về chính nó đã trở nên hơi tẻ nhạt. Tôi muốn có thể sử dụng một cái gì đó giống như chức năng return của Monad, tuy nhiên, tôi không biết bind sẽ làm gì cho các chức năng này, đặc biệt là vì tôi không bao giờ có ý định liên kết với bất kỳ thứ gì khác ngoài chức năng mà chúng trả về địa điểm đầu tiên.

Cố gắng bót đi giày này vào một đơn nguyên bắt đầu lo lắng cho tôi về việc có hay không những gì tôi đã làm được rất hữu ích, vì vậy, trong ngắn hạn, những gì tôi muốn biết là:

• phải là những gì tôi đang làm một Điều tồi tệ? nếu không,
• Tôi đang làm gì trước/sáng tạo lại bánh xe ở đây? nếu không,
• Có cách nào thanh lịch để thực hiện việc này hay tôi đã đạt được điều này và đang tham lam bằng cách muốn một số loại tương tự return?

(Ngẫu nhiên, bên cạnh đó, 'chức năng trả về chủ đề' hoặc 'cấu trúc dữ liệu đệ quy (chức năng)', tôi không biết loại mô hình này được gọi là gì và đã cố gắng thực hiện nghiên cứu hiệu quả trong nó khó khăn - nếu ai đó có thể cho tôi một tên cho mẫu này (nếu nó thực sự có một), thì điều đó sẽ rất hữu ích)

Answer 1

Để xem xét cấp cao, tôi muốn nói rằng loại của bạn đại diện cho một biến thể dòng trạng thái. Có gì một chút bối rối ở đây là loại hình được định nghĩa là

newtype R a = R (a , a -> R a) 

thay vì

newtype R a = R (a -> (R a, a)) 

đó sẽ là một chút tự nhiên hơn trong bối cảnh luồng vì bạn thường không "sản xuất" một cái gì đó nếu bạn chưa nhận được gì. chức năng của bạn sau đó sẽ có các loại đơn giản quá:

alpha, omage :: R String 
cascade :: R a -> [a] -> [a] 

Nếu chúng ta cố gắng khái quát ý tưởng này của một máy biến dòng, chúng tôi sớm nhận ra rằng trường hợp chúng ta chuyển đổi một danh sách các a s vào một danh sách các a s chỉ là một trường hợp đặc biệt. Với cơ sở hạ tầng phù hợp tại chỗ chúng tôi cũng có thể sản xuất một danh sách các số b s. Vì vậy, chúng tôi cố gắng khái quát các loại R:

newtype R a b = R (a -> (R a b, b)) 

Tôi đã nhìn thấy loại này của cấu trúc được gọi là Circuit, mà sẽ xảy ra là một full-blown arrow. Các mũi tên là một khái quát hóa khái niệm về các hàm và là một cấu trúc mạnh mẽ hơn so với các monads. Tôi không thể giả vờ hiểu được nền tảng lý thuyết thể loại, nhưng nó thực sự thú vị khi chơi với họ. Ví dụ, việc chuyển đổi không đáng kể chỉ Cat.id là:

import Control.Category 
import Control.Arrow 
import Prelude hiding ((.), id) 
import qualified Data.List as L 

-- ... Definition of Circuit and instances 

cascade :: Circuit a b -> [a] -> [b] 
cascade cir = snd . L.mapAccumL unCircuit cir 

-- 
ghci> cascade (Cat.id) [1,2,3,4] 
[1,2,3,4] 

Chúng tôi cũng có thể mô phỏng trạng thái bởi parameterizing mạch chúng ta trở lại như việc tiếp tục:

countingCircuit :: (a -> b) -> Circuit a (Int, b) 
countingCircuit f = cir 0 
    where cir i = Circuit $ \x -> (cir (i+1), (i, f x)) 

-- 
ghci> cascade (countingCircuit (+5)) [10,3,2,11] 
[(0,15),(1,8),(2,7),(3,16)] 

Và thực tế là loại mạch của chúng tôi là một phạm trù mang đến cho cho chúng tôi một cách hay để soạn các mạch:

ghci> cascade (countingCircuit (+5) . arr (*2)) [10,3,2,11] 
[(0,25),(1,11),(2,9),(3,27)] 

Answer 2

Tôi không có nhiều để thêm, ngoại trừ việc lưu ý rằng hàm cascade của bạn có thể được viết dưới dạng nếp gấp bên trái (và do đó cũng là một nếp gấp bên phải, mặc dù tôi chưa thực hiện chuyển đổi.)

cascade f = reverse . fst . foldl func ([], f) 
    where 
    func (rs,g) s = let R (r,h) = g s in (r:rs,h) 

Answer 3

Có vẻ như những gì bạn có là phiên bản luồng đơn giản. Đó là để nói, một đại diện của một dòng vô hạn các giá trị. Tôi không nghĩ rằng bạn có thể dễ dàng xác định điều này là một đơn nguyên, vì bạn sử dụng cùng một loại cho hạt giống của mình là cho các yếu tố của bạn, làm cho việc xác định fmap khó khăn (có vẻ như bạn cần phải đảo ngược chức năng được cung cấp cho fmap để có thể khôi phục hạt giống).Bạn có thể làm điều này một đơn nguyên bằng cách làm cho các loại hạt giống không phụ thuộc vào các loại nguyên tố như vậy

{-# LANGUAGE ExistentialQuantification #-} 
data Stream a = forall s. Stream a s (s -> Stream a) 

này sẽ cho phép bạn xác định một trường hợp Functor và Monad như sau

unfold :: (b -> (a, b)) -> b -> Stream a 
unfold f b = Stream a b' (unfold f) 
    where (a, b') = f b 

shead :: Stream a -> a 
shead (Stream a _ _) = a 

stail :: Stream a -> Stream a 
stail (Stream _ b f) = f b 

diag :: Stream (Stream a) -> Stream a 
diag = unfold f 
    where f str = (shead $ shead str, stail $ fmap stail str) 

sjoin :: Stream (Stream a) -> Stream a 
sjoin = diag 

instance Functor Stream where 
    fmap f (Stream a b g) = Stream (f a) b (fmap f . g) 

instance Monad Stream where 
    return = unfold (\x -> (x, x)) 
    xs >>= f = diag $ fmap f xs 

Lưu ý rằng chỉ này tuân theo luật Monad khi được xem là một tập hợp, vì nó không giữ nguyên thứ tự phần tử.

This giải thích đơn vị luồng sử dụng danh sách vô hạn, hoạt động tốt trong Haskell vì chúng có thể được tạo theo kiểu lười. Nếu bạn xem tài liệu cho loại Stream trong thư viện vector, bạn sẽ tìm phiên bản phức tạp hơn để có thể sử dụng nó trong quá trình hợp nhất luồng hiệu quả.