Pattern di ricorsione comune

Question

Mi sto abituando alle funzioni di ordine superiore di Haskell. Di solito posso sostituire schemi espliciti di ricorsione con funzioni come map, fold e scan. Tuttavia, ho spesso incontrato il seguente schema di ricorsione, che non capisco come esprimere utilizzando le funzioni di ordine superiore:

f (x:[]) = k x 
    f (x:xs) = g x (f xs) 

Per esempio, supponiamo che io rappresento analitica tableaux. Poi creo un tipo di dati come ad esempio:

data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau) 

Se voglio convertire un elenco di Expr s in una struttura tableau, voglio una parte cui funzione potrebbe somigliare:

f (x:[]) = N x 
    f (x:xs) = S x (f xs) 

Ora, Vedo tre opzioni: (1) creare una funzione che decida, dato un tableau e una lista, se il prossimo ramo nel tableau dovrebbe essere un S o N (o B, ma ignoreremo tale caso); (2) utilizzare una funzione di ordine superiore per incapsulare il pattern di ricorsione di f; (3) utilizzare una funzione come f.

Quale sarebbe l'opzione migliore?

Answer 1

mi piacerebbe molto probabilmente utilizzare il seguente:

f xs = foldr g (k (last xs)) (init xs) 

Fondamentalmente significa che la fine della lista è sostituito dal k x quando si piega. Grazie alla valutazione pigra presente ovunque, funziona anche per liste infinite.

Esistono altre due soluzioni: l'aggiunta del caso vuoto e l'utilizzo di Maybe.

A) aggiungere bossolo:

Sarebbe meglio se f [] era ben definita.Quindi, si potrebbe scrivere la definizione come

f [] = c 
f (x:xs) = g x (f xs) 

che è f = foldr g c. Ad esempio, se si modifica

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau 

a

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau 

allora si può rappresentare solo elemento tableaux come S expr N, e la funzione è definita come uno-liner

f = foldr S N 

'la la migliore soluzione per quanto tempo il caso vuoto ha un senso.

B) utilizzare Forse:

D'altra parte, se f [] non può essere definita in modo razionale, è peggio. Le funzioni parziali sono spesso considerate brutte. Per renderlo totale, puoi utilizzare Maybe. Definisci

f [] = Nothing 
f [x] = Just (k x) 
f (x:xs) = Just (g x w) 
      where Just w = f xs 

È una funzione totale, è meglio.

Ma ora si può riscrivere la funzione in:

f [] = Nothing 
f (x:xs) = case f xs of 
       Nothing -> Just (k x) 
       Just w -> Just (g x w) 

che è una piega a destra:

addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux 
addElement x Nothing = Just (N x) 
addElement x (Just w) = Just (S x w) 

f = foldr addElement Nothing 

In generale, pieghevole è idiomatica e dovrebbe essere usato quando si forma il modello di ricorsione. Altrimenti usa la ricorsione esplicita o prova a riutilizzare i combinatori esistenti. Se c'è un nuovo pattern, crea un combinatore, ma solo se userai molto il pattern - altrimenti è eccessivo. In questo caso, il modello è piegato per gli elenchi non vuoti definiti da: data List a = End a | Cons a (List a).

Answer 2

Se ho capito la domanda correttamente, quindi ecco la mia valutazione delle opzioni:

1. è probabilmente un po 'brutto dover corrispondere il tableau fuori da sotto il costruttore (presumibilmente arbitrariamente complessa?) per scrivere quella funzione. Questo approccio sembra alquanto fragile, anche se probabilmente funzionerebbe perfettamente.

2. Non vedo la necessità di generalizzare lo schema, dato che è una funzione ricorsiva che opera su una struttura ricorsiva. L'introduzione di un modello di ordine superiore potrebbe (penso) offuscare la logica attuale dietro l'esecuzione di una traversata ricorsiva di questa struttura di dati.

3. Penso che questo abbia un buon senso. Come hai osservato, è un "pattern" ragionevolmente riconosciuto, ma penso che corrisponda bene alla descrizione dell'algoritmo per scriverlo esattamente in questo modo. Potrebbe non essere generalizzabile o riusabile, ma dato che è essenzialmente il punto cruciale dell'approccio algoritmico, penso che abbia senso scrivere i casi direttamente come hai fatto in una funzione come f. Questo sarebbe il mio approccio preferito.

Siamo spiacenti di non fornire una risposta particolarmente concreta, ma è una risposta abbastanza soggettiva, quindi date le tre opzioni di cui sopra, vorrei scegliere l'opzione 3 per motivi di chiarezza e leggibilità.