Pieghe multiple in una sola passata utilizzando la funzione tupla generica

Question

Come posso scrivere una funzione che richiede una tupla di funzioni di tipo ai -> b -> ai e restituisce una funzione che accetta una tupla di elementi di tipo ai, un elemento di tipo b e combina ciascuno degli elementi in una nuova tupla di ai:

Questa è la firma dovrebbe essere come

f :: (a1 -> b -> a1, a2 -> b -> a2, ... , an -> b -> an) -> 
    (a1, a2, ... , an) -> 
    b -> 
    (a1, a2, ... , an) 

Tale che:

f (min, max, (+), (*)) (1,2,3,4) 5 = (1, 5, 8, 20) 

Il punto di questo è così posso scrivere:

foldlMult' t = foldl' (f t) 

e poi fare qualcosa di simile:

foldlMult' (min, max, (+), (*)) (head x, head x, 0, 0) x 

da fare molteplici pieghe in un solo passaggio. Le estensioni GHC vanno bene.

Answer 1

Se ho capito bene i vostri esempi, i tipi sono ai -> b -> ai, non ai -> b -> a come avete scritto per la prima volta. Riscriviamo i tipi a a -> ri -> ri, solo perché mi aiuta a pensare.

La prima cosa da osservare è questa corrispondenza:

(a -> r1 -> r1, ..., a -> rn -> rn) ~ a -> (r1 -> r1, ..., rn -> rn) 

Questo permette di scrivere queste due funzioni, che sono inverse:

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (r1 -> r1, r2 -> r2) 
pullArg (f, g) = \a -> (f a, g a) 

pushArg :: (a -> (r1 -> r1, r2 -> r2)) -> (a -> r1 -> r1, a -> r2 -> r2) 
pushArg f = (\a -> fst (f a), \a -> snd (f a)) 

Seconda osservazione: i tipi di forma ri -> ri sono a volte chiamati endomorfismi e ognuno di questi tipi ha un monoide con composizione come operazione associativa e funzione di identità come identità. Il pacchetto Data.Monoid ha questo wrapper per questo: si

newtype Endo a = Endo { appEndo :: a -> a } 

instance Monoid (Endo a) where 
    mempty = id 
    mappend = (.) 

Questo permette di riscrivere la precedente pullArg a questo:

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (Endo r1, Endo r2) 
pullArg (f, g) = \a -> (Endo $ f a, Endo $ g a) 

Terza osservazione: il prodotto di due monoidi è anche un monoide, di cui al presente esempio anche da Data.Monoid:

instance (Monoid a, Monoid b) => Monoid (a, b) where 
    mempty = (mempty, mempty) 
    (a, b) `mappend` (c, d) = (a `mappend` c, b `mappend d) 

Analogamente per le tuple di qualsiasi numero di argomenti.

Quarta osservazione: What are folds made of? Risposta: folds are made of monoids!

import Data.Monoid 

fold :: Monoid m => (a -> m) -> [a] -> m 
fold f = mconcat . map f 

Questo fold è solo una specializzazione di foldMap da Data.Foldable, quindi in realtà non abbiamo bisogno di definirlo, possiamo semplicemente importare la sua versione più generale:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m 

Se fold con Endo, che è lo stesso di piegare da destra.Per piegare da sinistra, si vuole piegare con la Dual (Endo r) monoide:

myfoldl :: (a -> Dual (Endo r)) -> r -> -> [a] -> r 
myfoldl f z xs = appEndo (getDual (fold f xs)) z 


-- From `Data.Monoid`. This just flips the order of `mappend`. 
newtype Dual m = Dual { getDual :: m } 

instance Monoid m => Monoid (Dual m) where 
    mempty = Dual mempty 
    Dual a `mappend` Dual b = Dual $ b `mappend` a 

Ricordate la nostra funzione pullArg? Facciamo rivedere un po 'di più, dal momento che si sta piegando da sinistra:

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> Dual (Endo r1, Endo r2) 
pullArg (f, g) = \a -> Dual (Endo $ f a, Endo $ g a) 

E questo, io sostengo, è la versione 2-tuple del f, o almeno isomorfo ad esso. È possibile riconfigurare le funzioni piega nella forma a -> Endo ri, e poi fare:

let (f'1, ..., f'n) = foldMap (pullArgn f1 ... fn) xs 
in (f'1 z1, ..., f'n zn) 

vale la pena anche guardare: Composable Streaming Folds, che è una ulteriore elaborazione di queste idee.

Answer 2

Per un approccio diretto, si può solo definire le equivalenti di Control.Arrow s' (***) e (&&&) esplicitamente, per ogni N (ad es N == 4):

prod4 (f1,f2,f3,f4) (x1,x2,x3,x4) = (f1 x1,f2 x2,f3 x3,f4 x4) -- cf (***) 
call4 (f1,f2,f3,f4) x   = (f1 x, f2 x, f3 x, f4 x) -- cf (&&&) 
uncurry4 f  (x1,x2,x3,x4) = f x1 x2 x3 x4 

Poi,

foldr4 :: (b -> a1 -> a1, b -> a2 -> a2, 
      b -> a3 -> a3, b -> a4 -> a4) 
     -> (a1, a2, a3, a4) -> [b] 
     -> (a1, a2, a3, a4)      -- (f .: g) x y = f (g x y) 
foldr4 t z xs = foldr (prod4 . call4 t) z xs  -- foldr . (prod4 .: call4) 
       -- f x1 (f x2 (... (f xn z) ...)) -- foldr . (($) .: ($)) 

Così il le funzioni di tuple nelle versioni foldr4 sono le versioni girate di ciò che volevi. Test:

Prelude> g xs = foldr4 (min, max, (+), (*)) (xs xs testa, testa, 0, 1) xs
Prelude> g [1..5]
(1,5,15,120)

foldl4' è un aggiustamento di distanza. Dal momento che

foldr f z xs == foldl (\k x r-> k (f x r)) id xs z 
foldl f z xs == foldr (\x k a-> k (f a x)) id xs z 

abbiamo

foldl4, foldl4' :: (t -> a -> t, t1 -> a -> t1, 
        t2 -> a -> t2, t3 -> a -> t3) 
       -> (t, t1, t2, t3) -> [a] 
       -> (t, t1, t2, t3) 
foldl4 t z xs = foldr (\x k a-> k (call4 (prod4 t a) x)) 
         (prod4 (id,id,id,id)) xs z 
foldl4' t z xs = foldr (\x k a-> k (call4 (prod4' t a) x)) 
         (prod4 (id,id,id,id)) xs z 
prod4' (f1,f2,f3,f4) (x1,x2,x3,x4) = (f1 $! x1,f2 $! x2,f3 $! x3,f4 $! x4) 

Abbiamo anche ottenuto i tipi come si voleva, per le funzioni del tuple.

È necessario utilizzare una versione più rigida di prod4 per forzare gli argomenti all'inizio di foldl4'.