È possibile definire una funzione "opposta" di ordine superiore caso per caso?

Question

Sono un principiante Haskell. Sto cercando di creare un mini-linguaggio all'interno di Haskell e vorrei possibilmente avere una funzione di ordine superiore chiamata opp (abbreviazione di "opposto") che converta un numero di funzioni familiari nei loro opposti evidenti. Ad esempio, opp succ sarebbe la funzione pred, opp head sarebbe last e così via. Non ho una definizione generale di cosa significhi convertire una funzione nel suo opposto: voglio solo scegliere alcuni esempi chiave e dichiarare quali sono i loro opposti. Quindi voglio una funzione altamente polimorfa che non viene quasi mai definita.

La difficoltà sembra essere che voglio riconoscere le funzioni con il loro nome piuttosto che con le loro essenze (per così dire). Una manifestazione di questa difficoltà è che se scrivo

opp succ = pred

quindi Haskell tratta succ come una variabile e quindi mi dà una funzione costante che prende sempre il valore pred. Quello che voglio veramente è di dire qualcosa di più simile a "Se vedi mai la stringa opp succ allora pensa a un altro nome per pred". Ma dopo aver cercato in giro per un po ', non riesco a scoprire come farlo (se è possibile a tutti).

In sintesi, vorrei definire una funzione

opp :: (a -> b) -> (a -> b)

da dire cose come

opp succ = pred

opp pred = succ

opp head = last

opp last = head

e aggiungere a questa lista ogni volta che ne ho voglia. Ovviamente non posso farlo in quel modo, ma c'è un modo non orribile per ottenere lo stesso effetto?

Answer 1

Potrebbe essere possibile utilizzare una sorta di mappa di hash basata sull'indirizzo delle chiusure nell'heap per identificare le funzioni. Quindi è possibile creare una tabella di questo tipo. Sfortunatamente, non otterresti veramente ciò che desideri, poiché le funzioni sono solo valori e in quanto tali vengono create ogni volta che il compilatore (o il runtime) decide di farlo.

E.g. anche quando dici che

opp head = last 

Si potrebbe (a seconda dell'implementazione del compilatore) ottenere nulla per

opp (λx.head x) 

In realtà, non si dispone di un'identità affidabile sui valori di funzionalità - quindi penso che ci sia nessun modo utilizzabile per fare ciò che intendi fare.

Answer 2

Se riformulare la tua domanda in questa forma il problema può diventare più chiaro a voi:

opp x | x == succ = pred 
     | x == pred = succ 

questo vi darà l'errore che (a -> b) non ha Eq esempio, che non può avere in quanto l'uguaglianza per le funzioni è non definito.

Una soluzione a questo sarebbe definire un tipo di dati separato su cui è possibile eseguire la corrispondenza.

Answer 3

Sì, è possibile, tuttavia è necessario RankNTypes per avere una buona implementazione.

{-# LANGUAGE TypeOperators #-} 
{-# LANGUAGE RankNTypes #-} 
module Opposites where 

class Opposite f where 
    makeOpposite :: (a -> b) -> (a -> b) -> f a b 


data FunctionAndOpposite a b = FunctionAndOpposite (a -> b) (a -> b) 

instance Opposite (->) where 
    makeOpposite = const 

instance Opposite FunctionAndOpposite where 
    makeOpposite = FunctionAndOpposite 

opp :: FunctionAndOpposite a b -> a -> b 
opp (FunctionAndOpposite _ f) = f 

type a :<-> b = forall f. Opposite f => f a b 

succ' :: Enum a => a :<-> a 
succ' = makeOpposite succ pred 

pred' :: Enum a => a :<-> a 
pred' = makeOpposite pred succ 

head' :: [a] :<-> a 
head' = makeOpposite head last 

last' :: [a] :<-> a 
last' = makeOpposite last head 

Esempio utilizzo:

> head' [1,2,3] 
1 
> opp head' [1,2,3] 
3 

Come funziona

primo luogo, v'è la classe Opposite. Questo descrive solo un f a b che può essere costruito con due funzioni di (a -> b) (le funzioni normale e opposta).

Successivamente, è definito un tipo di dati FunctionAndOpposite. Questo memorizza solo le due funzioni. Ora sia la funzione standard, e questo sono fatti esempi della classe Opposite. L'istanza della funzione elimina semplicemente la funzione opposta.

Ora è possibile definire la funzione opp. Questo prende solo la seconda funzione da un FunctionAndOpposite.

Infine otteniamo la linea che unisce tutti:

type a :<-> b = forall f. Opposite f => f a b 

cosa definisce un tipo sinonimi che richiede due tipi di ingresso A e B, quindi restituisce un tipo f a b, dove f può essere qualsiasi Opposite (dipende da cosa è necessario).

(lo :<-> è solo un nome di fantasia per il tipo abilitato con TypeOperators).

Prendere in considerazione il codice head' [1,2,3]. head' ha il tipo forall f. Opposite f => f [a] a. Tuttavia, poiché viene utilizzato come applicazione di funzione (poiché ha un argomento subito dopo), f deve essere ->. Pertanto, viene utilizzata l'implementazione della funzione Opposite, restituendo il primo argomento a makeOpposite, che è head (ottimo!).

Tuttavia, diciamo che si chiama opp head' [1,2,3]. opp ha il tipo FunctionAndOpposite a b -> a -> b, quindi f deve essere FunctionAndOpposite. Pertanto, viene chiamata l'istanza di Opposite, creando il tipo di dati utilizzando entrambi gli argomenti su makeOpposite. opp quindi estrae la seconda funzione, che è last.

---

Per inciso, questo viene fatto utilizzando una tecnica simile a quello utilizzato nella biblioteca lens per Isomorphism.Un isomorfismo è fondamentalmente una coppia di funzioni che sono inverse l'una dall'altra. Per esempio (+2) e (-2), reverse e se stesso. Questo è probabilmente un concetto più utile in generale, poiché consente di eseguire operazioni su un tipo di dati su una trasformazione. Vedere Control.Lens.Iso per ulteriori dettagli, tuttavia si noti che per capire questo è necessario comprendere i concetti dell'obiettivo, che è un lavoro piuttosto grande.