Haskell: ¿Entiendo mal cómo se pueden usar las flechas?

Question

Escribí un código de juguete para jugar con el concepto de Flechas. Quería ver si podía escribir una Flecha que codificara el concepto de una función con estado, dando un valor diferente después de diferentes llamadas.

{-# LANGUAGE Arrows#-} 
module StatefulFunc where 

import Control.Category 
import Control.Arrow 

newtype StatefulFunc a b = SF { unSF :: a -> (StatefulFunc a b, b) } 

idSF :: StatefulFunc a a 
idSF = SF $ \a -> (idSF, a) 

dotSF :: StatefulFunc b c -> StatefulFunc a b -> StatefulFunc a c 
dotSF f g = SF $ \a -> 
    let (g', b) = unSF g a 
     (f', c) = unSF f b 
    in (dotSF f' g', c) 

instance Category StatefulFunc where 
    id = idSF 
    (.) = dotSF 

arrSF :: (a -> b) -> StatefulFunc a b 
arrSF f = ret 
    where ret = SF fun 
     fun a = (ret, f a) 

bothSF :: StatefulFunc a b -> StatefulFunc a' b' -> StatefulFunc (a, a') (b, b') 
bothSF f g = SF $ \(a,a') -> 
    let (f', b) = unSF f a 
     (g', b') = unSF g a' 
    in (bothSF f' g', (b, b')) 

splitSF :: StatefulFunc a b -> StatefulFunc a b' -> StatefulFunc a (b, b') 
splitSF f g = SF $ \a -> 
    let (f', b) = unSF f a 
     (g', b') = unSF g a 
    in (splitSF f' g', (b, b')) 

instance Arrow StatefulFunc where 
    arr = arrSF 
    first = flip bothSF idSF 
    second = bothSF idSF 
    (***) = bothSF 
    (&&&) = splitSF 

eitherSF :: StatefulFunc a b -> StatefulFunc a' b' -> StatefulFunc (Either a a') (Either b b') 
eitherSF f g = SF $ \e -> case e of 
     Left a -> let (f', b) = unSF f a in (eitherSF f' g, Left b) 
     Right a' -> let (g', b') = unSF g a' in (eitherSF f g', Right b') 

mergeSF :: StatefulFunc a b -> StatefulFunc a' b -> StatefulFunc (Either a a') b 
mergeSF f g = SF $ \e -> case e of 
     Left a -> let (f', b) = unSF f a in (mergeSF f' g, b) 
     Right a' -> let (g', b) = unSF g a' in (mergeSF f g', b) 

instance ArrowChoice StatefulFunc where 
    left = flip eitherSF idSF 
    right = eitherSF idSF 
    (+++) = eitherSF 
    (|||) = mergeSF 

Así que después de pasar por las distintas definiciones de clase de tipo (no estoy seguro si o cómo ArrowZero trabajaría para esto, así que lo saltamos), he definido algunas funciones auxiliares

evalSF :: (StatefulFunc a b) -> a -> b 
evalSF f a = snd (unSF f a) 

givenState :: s -> (s -> a -> (s, b)) -> StatefulFunc a b 
givenState s f = SF $ \a -> let (s', b) = f s a in (givenState s' f, b) 

Y funcionó un ejemplo de uso

count :: StatefulFunc a Integer 
count = givenState 1 $ \c _ -> (c+1, c) 

countExample :: StatefulFunc a Integer 
countExample = proc _ -> do 
        (count', one) <- count -<() 
        (count'', two) <- count' -<() 
        (count''', three) <- count'' -<() 
        returnA -< three 

Sin embargo, cuando intento compilar countExample, me sale "no incluidos en" errores de count' y count'', lo que supongo significa que necesito volver al tutorial y leer lo que se puede usar cuando. Creo que lo que realmente me gustaría de todos modos es algo más parecido a

countExample :: Integer 
countExample = 
    let (count', one) = unSF count() 
     (count'', two) = unSF count'() 
     (count''', three) = unSF count''() 
    in three 

Pero eso es un poco raro, y esperaba algo un poco más natural.

¿Alguien puede explicar cómo estoy entendiendo mal cómo funcionan las flechas, y cómo se pueden usar? ¿Hay alguna filosofía fundamental para Arrows que me pierda?

Answer 1

¿Alguien puede explicar cómo estoy entendiendo mal cómo funcionan las flechas, y cómo se pueden utilizar? ¿Hay alguna filosofía fundamental para Arrows que me pierda?

Tengo la impresión de que está tratando este Arrow como lo haría con un Monad. No sé si esto cuenta como una "filosofía fundamental", pero hay una diferencia significativa entre los dos, a pesar de la frecuencia con la que se superponen. En cierto sentido, la clave que define un Monad es la función join; cómo colapsar una estructura anidada en una sola capa. Son útiles por lo que permite join: puede crear nuevas capas monádicas en una función recursiva, alterar la estructura Functor en función de su contenido, y así sucesivamente. Pero esto no se trata de Monad s, así que lo dejamos así.

La esencia de un Arrow, por otro lado, es una versión generalizada de una función. La clase de tipo Category define versiones generalizadas de la composición de funciones y la función de identidad, mientras que la clase de tipo Arrow define cómo levantar una función normal a Arrow y cómo trabajar con Arrow que toman múltiples argumentos (en forma de tuplas-- Arrows no necesariamente se puede curry!).

Al combinar Arrow s de una manera básica, al igual que en su primera función countExample, todo lo que estamos haciendo en realidad es algo así como la composición de funciones elaborada . Revise su definición de (.): está tomando dos funciones con estado y conectándolas a una única función con estado, con el comportamiento de cambio de estado manejado automáticamente.

Por lo tanto, el principal problema con su countExample es que incluso menciona count' y tal.Todo esto se hace detrás de las escenas, al igual que no es necesario pasar explícitamente el parámetro de estado junto con la notación do en la mónada State.

Ahora, debido a la notación proc simplemente le permite construir grandes compuestas Arrow s, que en realidad uso de su función de estado que necesita para trabajar fuera de la sintaxis Arrow, al igual que lo necesita o runState tales con el fin de ejecutar realmente un cálculo en la mónada State. Su segundo countExample es en este sentido, pero demasiado especializado. En el caso general, la función de estado asigna una corriente de insumos a una corriente de salidas , lo que es un finite state transducer, por lo runStatefulFunction probablemente tomaría una lista perezosa de valores de entrada y convertirlos en una lista perezosa de valores de salida usando un doblez derecho con unSF para alimentar a cada uno al transductor por turno.

Si desea ver un ejemplo, el paquete de arrowsincludes an Arrow transformer Automaton que define algo casi idéntico a su StatefulFunction, excepto con un arbitraria Arrow en lugar de la función normal que haya utilizado.

---

Ah, y volver a examinar brevemente la relación entre Arrow s y Monad s:

Llanura Arrows son únicas cosas tipo función "de primer orden". Como dije antes, no siempre se pueden curry, y tampoco se pueden "aplicar" siempre en el mismo sentido en que la función ($) aplica funciones. Si realmente desea un orden superior Arrows, la clase de tipo ArrowApply define una aplicación Arrow. Esto agrega gran oferta de potencia a un Arrow y, entre otras cosas, permite la misma característica de "estructura anidada de colapso" que proporciona Monad, lo que permite definir generalmente una instancia Monad para cualquier instancia ArrowApply.

En la otra dirección, ya que Monad s permiten la combinación de funciones que crean nueva estructura monádica, para cualquier Monadm se puede hablar de una "Kleisli flecha", que es una función del tipo a -> m b. Las flechas Kleisli para Monad pueden tener una instancia Arrow de una manera bastante obvia.

Aparte de ArrowApply y flechas Kleisli, no hay una relación particularmente interesante entre las clases de tipos.