Czy istnieje elegancki sposób na funkcje zwracające funkcje tego samego typu (w krotce)

Question

Używam haskell do wdrożenia wzorca obejmującego funkcje, które zwracają wartość, i siebie (lub funkcja tego samego typu). Teraz I zostały wdrożone to tak:

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) 

Siłą napędową tego rodzaju funkcji jest funkcja o nazwie Kaskada:

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

który odbywa funkcję nasion oraz listę i zwraca listę utworzoną przez zastosowanie funkcji seed do pierwszego elementu listy, zastosowanie zwróconej przez nią funkcji do drugiego elementu listy i tak dalej.

To działa - jednak w procesie korzystania z tego dla nieco bardziej użytecznych rzeczy zauważyłem, że wiele razy miałem podstawowe jednostki, które są funkcjami, które zwracały funkcje inne niż one same rzadko; i jawne deklarowanie funkcji, która się zwraca, stawało się nieco nudne. Wolałbym użyć czegoś podobnego do funkcji Monada, return, jednak nie mam pojęcia, co zrobiłby dla tego typu funkcji bind, zwłaszcza że nigdy nie zamierzałem, aby były one powiązane z czymkolwiek innym niż funkcją, którą zwracają w pierwsze miejsce.

Próbując shoehorn tego do monady zaczęli martwić się o mnie, czy nie, co robiłem było przydatne, tak, w skrócie, co chcę wiedzieć, to:

• Czy to, co robię Zła rzecz? jeśli nie,
• Czy to, co robię, robiłem wcześniej? Czy wymyślam tutaj nowe koło? jeśli nie, to czy istnieje elegancki sposób, aby to zrobić, czy też już to osiągnąłem i jestem chciwy, żądając pewnego rodzaju analogu return?

(Nawiasem mówiąc, poza tym, funkcje, które "zwracają się same" lub "struktura danych rekursywnych (funkcji)", nie jestem do końca pewien, jak nazywa się ten rodzaj wzorca, i podjęto próbę przeprowadzenia skutecznych badań w tym jest trudne - jeśli ktokolwiek mógłby podać mi nazwę tego wzoru (jeśli takowy rzeczywiście istnieje), to sam byłby bardzo pomocny)

Answer 1

Biorąc pod uwagę wysoki poziom, powiedziałbym, że twój typ reprezentuje transformator strumieniowy. Co jest nieco mylące jest to, że Twój typ jest zdefiniowany jako

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

zamiast

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

który byłby nieco bardziej naturalne w kontekście przesyłania strumieniowego, ponieważ zazwyczaj nie „produkują” jeśli coś jeszcze nic nie dostałeś. Twoje funkcje musiałaby wówczas prostszych rodzajów też:

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

Jeśli staramy się uogólnić tę ideę transformatora strumienia, szybko sobie sprawę, że w przypadku, gdy przekształcamy listę a s do listy a s jest po prostu specjalny przypadek. Przy odpowiedniej infrastrukturze możemy równie dobrze wyprodukować listę b. Więc staramy się uogólniać typ R:

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

widziałem tego rodzaju struktury miano Circuit, co dzieje się pełnowymiarową arrow. Strzałki są uogólnieniem koncepcji funkcji i są jeszcze potężniejszą konstrukcją niż monady. Nie mogę udawać, że rozumiem kategorię - tło teoretyczne, ale zdecydowanie warto się z nimi bawić. Na przykład, trywialne transformacja jest tylko Cat.id:

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] 

Możemy również symulować stan przez parametryzacji obwód wracamy jako kontynuacja:

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)] 

i fakt, że nasz typ układu jest to kategoria daje nam dobry sposób na komponowanie obwodów:

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

Answer 2

Nie mam wiele do dodania, z wyjątkiem uwagi, że twoja funkcja cascade można zapisać jako lewy fałd (a więc również jako prawy fałd, chociaż nie wykonałem transformacji).

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

Answer 3

Wygląda na to, że masz uproszczoną wersję strumienia. To znaczy, że reprezentuje nieskończony strumień wartości. Nie sądzę, że możesz łatwo zdefiniować to jako monadę, ponieważ używasz tego samego typu dla swojego nasionka co dla twoich elementów, co utrudnia zdefiniowanie fmap (wydaje się, że musisz musiał odwrócić funkcję dostarczoną do fmap aby móc odzyskać ziarno).Można zrobić to monady poprzez rodzaj nasion niezależnie od typu elementu jak tak

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

Pozwoli to na zdefiniowanie Functor i Monad instancji następująco

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 

Zauważ, że to tylko przestrzega praw Monady, gdy jest postrzegany jako zestaw, ponieważ nie zachowuje porządku elementu.

This wyjaśnienie z monady strumienia korzysta nieskończone list, który działa tak samo dobrze w Haskell ponieważ mogą być generowane w leniwe mody. Jeśli przejrzysz dokumentację dla typu Stream w bibliotece vector, znajdziesz , aby znaleźć bardziej skomplikowaną wersję, dzięki czemu można go wykorzystać do wydajnego scalania strumienia.