2014-12-27 22 views
45

che sto cercando di capire il risultato diCosa succede quando compongo * con + in Haskell?

(*) . (+) 

in Haskell. So che l'operatore composizione è solo la composizione di serie di funzioni-matematica in modo

(f . g) = f (g x) 

Ma:

(*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a 

sto lottando per capire questo tipo di firma. Mi sarei aspettato di essere in grado di fare cose del tipo:

((*) . (+)) 1 2 :: Num a => a -> a 
= (* (+ 1 2)) 

Qual è il significato di (*). (+) firma del tipo? Ho provato a giocare con qualcosa di simile (giusto la corrispondenza con la sua firma):

((*) . (+)) 1 (\x -> x + 1) 1 

Ma questo non riesce a compilare. Sto provando a seguire i passaggi logici durante la composizione di questi, ma non capisco completamente come si arriva a questo risultato (e quale sia il risultato ).

risposta

67

Capisco come ti senti. Ho trovato la composizione della funzione abbastanza difficile da afferrare in un primo momento. Ciò che mi ha aiutato ad aggirare la questione sono state le firme di tipo. Si consideri:

(*) :: Num x => x -> x -> x 
(+) :: Num y => y -> y -> y 
(.) :: (b -> c) -> (a -> b) -> a -> c 

Ora, quando si scrive (*) . (+) in realtà è lo stesso di (.) (*) (+) (cioè (*) è il primo argomento di (.) e (+) è il secondo argomento a (.)):

(.) :: (b -> c) -> (a -> b) -> a -> c 
     |______| |______| 
      |   | 
      (*)   (+) 

Quindi il tipo firma di (*) (esNum x => x -> x -> x) unifica con b -> c:

(*) :: Num x => x -> x -> x -- remember that `x -> x -> x` 
       | |____| -- is implicitly `x -> (x -> x)` 
       |  | 
       b -> c 

(.) (*) ::   (a -> b) -> a -> c 
          |    | 
          |   |‾‾‾‾| 
      Num x =>  x   x -> x 

(.) (*) :: Num x => (a -> x) -> a -> x -> x 

qui la firma di tipo (+) (cioè Num y => y -> y -> y) unifica con Num x => a -> x:

(+) :: Num y => y -> y -> y -- remember that `y -> y -> y` 
       | |____| -- is implicitly `y -> (y -> y)` 
       |  | 
     Num x => a -> x 

(.) (*) (+) :: Num x    => a ->  x -> x 
             |  |   | 
             |  |‾‾‾‾|  |‾‾‾‾| 
           Num y => y  y -> y  y -> y 

(.) (*) (+) :: (Num (y -> y), Num y) => y -> (y -> y) -> y -> y 

Spero che chiarisce dove il Num (y -> y) e Num y provengono. Ti rimane una funzione molto strana del tipo (Num (y -> y), Num y) => y -> (y -> y) -> y -> y.

Ciò che lo rende così strano è che si aspetta che sia e y -> y siano istanze di Num. È comprensibile che debba essere un'istanza di Num, ma come y -> y? Creare y -> y un'istanza di Num sembra illogico. Questo non può essere corretto.

Tuttavia, ha senso quando si guarda a ciò che realmente fa la composizione funzione:

(f . g) = \z -> f (g z) 

((*) . (+)) = \z -> (*) ((+) z) 

in modo da avere una funzione \z -> (*) ((+) z). Quindi, z deve essere chiaramente un'istanza di Num perché a esso viene applicato (+). Quindi il tipo di \z -> (*) ((+) z) è Num t => t -> ... dove ... è il tipo di (*) ((+) z), che troveremo in un momento.

Pertanto ((+) z) è del tipo Num t => t -> t perché richiede un altro numero. Tuttavia, prima che venga applicato a un altro numero, viene applicato (*).

Quindi (*) aspetta ((+) z) essere un'istanza di Num, motivo per cui t -> t dovrebbe essere un'istanza di Num. Pertanto, lo ... viene sostituito da (t -> t) -> t -> t e il vincolo Num (t -> t) viene aggiunto, risultando nel tipo (Num (t -> t), Num t) => t -> (t -> t) -> t -> t.

Il modo in cui si vuole veramente coniugare (*) e (+) sta usando (.:):

(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d 
f .: g = \x y -> f (g x y) 

Quindi (*) .: (+) è lo stesso di \x y -> (*) ((+) x y). Ora vengono forniti due argomenti a (+) assicurando che ((+) x y) sia effettivamente solo Num t => t e non Num t => t -> t.

Quindi ((*) .: (+)) 2 3 5 è (*) ((+) 2 3) 5 che è (*) 5 5 che è 25, che credo sia quello che vuoi.

Nota che f .: g può anche essere scritto come (f .) . g e (.:) può anche essere definito come (.:) = (.) . (.). Si può leggere di più su di esso qui:

What does (f .) . g mean in Haskell?

Speranza che aiuta.

+0

Grazie per la vostra risposta espansiva. Sto provando ad attraversare ogni parte di esso e capire. Ad un certo punto si cita '(.) (*) :: (a -> b) -> a -> c', che diventa' Num x => (a -> x) -> a -> x -> x '. Da dove viene l'extra 'x'? Perché 'c' diventa' x -> x', e non solo 'x'? – user2666425

+0

@ user2666425 La freccia della funzione è associativa corretta. Ciò significa che le funzioni del tipo 'f :: a -> b -> c' sono * più esplicitamente * del tipo' f :: a -> (b -> c) '. Ciò segue l'intuizione che 'f' è una funzione che prende un argomento del tipo' a' e restituisce un'altra funzione 'g :: b -> c', che a sua volta prende un argomento del tipo' b' e restituisce un valore del tipo 'c'. Quindi quando unifiamo '(*) :: Num x => x -> x -> x' con' b -> c' stiamo naturalmente unificando 'Num x => x -> (x -> x)' con ' b -> c'. Quindi 'b' si unifica con' x' e 'c' si unifica con' x -> x'. Spero possa aiutare. =) –

+0

Se vuoi capire come funziona l'unificazione, allora questa risposta potrebbe aiutarti: http://stackoverflow.com/a/27117861/783743 –

9

(*) e (+) entrambi hanno il tipo di firma Num a => a -> a -> a Ora, se li componi, ottieni qualcosa di funky.

(*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a 

Questo perché (*) e (+) si aspettano due 'argomenti'.

(+) con un argomento ottiene una funzione. L'operatore . si aspetta tale funzione (lo a -> a che vedi).

Ecco il significato di (*) . (+)

         x  f   y 
(*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a 

(*) . (+) mappe x f y-((x +) * f) y dove f è una funzione a-a che è anche un numero. Il motivo per cui una funzione è (*) prevede che i tipi corrispondano mentre si aspettano due argomenti, ma quella funzione deve essere un numero perché (*) funziona solo sui numeri.

In realtà, questa funzione non ha alcun senso.

2

Let:

m = (*) 
a = (+) 

poi

(m.a) x = (m (a x)) = m (a x) 

Ora m aspetta una Num a come parametro, invece (a x), cioè (x +) è una funzione unaria (a -> a) per definizione di (+). Immagino che quello che è successo è che GHC cerca di unire questi due tipi in modo che, se si ha un tipo che è sia un numero che una funzione unaria, m può prendere un numero e una funzione unaria e restituire una funzione unaria, poiché sono considerati lo stesso tipo

Come indicato da @Syd, questa unificazione non avrebbe senso per qualsiasi tipo di numero normale come numeri interi e numeri in virgola mobile.

7

Alcune estensioni primi:

{-# LANGUAGE FlexibleContexts, FlexibleInstances, TypeSynonymInstances #-} 

Come le altre risposte mostrano, la vostra funzione è

weird :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a 
weird x g = (x +) * g 

Ma questa funzione ha una semantica non strane.

C'è una nozione di difference lists. Di conseguenza, esiste una nozione di differenza di numeri interi. Li ho visti essere utilizzati solo nell'impostazione tipizzata in modo dipendente (ad esempio here, ma non è l'unico caso). La parte rilevante della definizione è

instance Enum DiffInt where 
    toEnum n = (n +) 
    fromEnum n = n 0 

instance Num DiffInt where 
    n + m = n . m 
    n * m = foldr (+) id $ replicate (fromEnum n) m 

Questo non ha molto senso in Haskell, ma può essere utile con tipi dipendenti.

Ora possiamo scrivere

test :: DiffInt 
test = toEnum 3 * toEnum 4 

O

test :: DiffInt 
test = weird 3 (toEnum 4) 

In entrambi i casi fromEnum test == 12.

EDIT

E 'possibile evitare l'utilizzo dell'estensione TypeSynonymInstances:

{-# LANGUAGE FlexibleContexts, FlexibleInstances #-} 

weird :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a 
weird x g = (x +) * g 

instance (Enum a, Num a) => Enum (a -> a) where 
    toEnum n = (toEnum n +) 
    fromEnum n = fromEnum $ n (toEnum 0) 

instance (Enum a, Num a) => Num (a -> a) where 
    n + m = n . m 
    n * m = foldr (+) id $ replicate (fromEnum n) m 

type DiffInt = Int -> Int 

Come prima possiamo scrivere

test' :: DiffInt 
test' = weird 3 (toEnum 4) 

ma ora possiamo anche scrivere

-- difference ints over difference ints 
type DiffDiffInt = DiffInt -> DiffInt 

test'' :: DiffDiffInt 
test'' = weird (toEnum 3) (toEnum (toEnum 4)) 

E

main = print $ fromEnum $ fromEnum test' 

stampe 12.

EDIT2 Link ottimali aggiunti.

+0

Dobbiamo assumere 'newtype DiffInt = DiffInt {getDiffInt :: Int -> Int}'? –

+0

Inoltre, la definizione completa minima di 'Num' è:' (+), (*), abs, signum, fromInteger, (negate | (-)) ': http://hackage.haskell.org/package/base -4.7.0.2/docs/Prelude.html # t: Num –

+0

@Aadit M Shah, il codice [compila] (http://ideone.com/OFdpK0). Conosco la definizione completa minima di 'Num', ecco perché mi viene detta" la parte rilevante ". – user3237465

2

Ci sono buone risposte qui, ma permettetemi di indicare rapidamente alcuni passaggi in cui avete sbagliato.

In primo luogo, la definizione corretta di composizione funzione è

(f . g) x = f (g x) 

si omessi il x sul lato sinistro. Successivamente, dovresti ricordare che in Haskell h x y corrisponde a (h x) y. Quindi, contrariamente a quanto ti aspettavi,

((*) . (+)) 1 2 = (((*) . (+)) 1) 2 = ((*) ((+) 1)) 2 = ((+) 1) * 2, 

e ora capisci perché non funziona. Inoltre,

((*) . (+)) 1 (\x -> x + 1) 1 

non funziona, perché il vincolo Num (Int -> Int) non è soddisfatto.

Problemi correlati