Haskell Language
펑터
수색…
소개
Functor
는 covariantly 매핑 될 수있는 f :: * -> *
형식의 클래스입니다. 데이터 구조를 통해 함수를 매핑하면 구조 자체를 변경하지 않고 구조의 모든 요소에 함수를 적용합니다.
비고
Functor는 어떤 가치를위한 컨테이너 또는 계산 컨텍스트로 생각할 수 있습니다. 예는 Maybe a
또는 [a]
입니다. Typeclassopedia 기사에는 Functors 의 개념을 잘 설명하고 있습니다.
실제 Functor로 간주되기 위해 인스턴스는 다음 2 가지 법률을 존중해야합니다.
정체
fmap id == id
구성
fmap (f . g) = (fmap f) . (fmap g)
Functor의 일반적인 인스턴스
아마도
Maybe
가능성이없는 값을 포함하는 Functor
가있을 수 있습니다.
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
Maybe
Functor
의 인스턴스는 Just
싸여있는 값에 함수를 적용합니다. 계산이 이전에 실패한 경우 (즉, Maybe
값이 Nothing
임) 함수를 적용 할 값이 없기 때문에 fmap
은 아무 작업도하지 않습니다.
> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing
우리는 동등한 추론을 사용하여이 인스턴스의 펑터 법칙을 검사 할 수 있습니다. 정체성 법 (identity law)
fmap id Nothing
Nothing -- definition of fmap
id Nothing -- definition of id
fmap id (Just x)
Just (id x) -- definition of fmap
Just x -- definition of id
id (Just x) -- definition of id
구성법에있어서,
(fmap f . fmap g) Nothing
fmap f (fmap g Nothing) -- definition of (.)
fmap f Nothing -- definition of fmap
Nothing -- definition of fmap
fmap (f . g) Nothing -- because Nothing = fmap f Nothing, for all f
(fmap f . fmap g) (Just x)
fmap f (fmap g (Just x)) -- definition of (.)
fmap f (Just (g x)) -- definition of fmap
Just (f (g x)) -- definition of fmap
Just ((f . g) x) -- definition of (.)
fmap (f . g) (Just x) -- definition of fmap
기울기
목록의 Functor
인스턴스는 목록의 모든 값에 기능을 적용합니다.
instance Functor [] where
fmap f [] = []
fmap f (x:xs) = f x : fmap f xs
이것은 대안 적으로 list comprehension으로 쓰여질 수 있습니다 : fmap f xs = [fx | x <- xs]
.
이 예제는 fmap
generalises map
보여준다. map
은 목록에서만 작동하지만 fmap
은 임의 Functor
에서 작동합니다.
정체성 법칙은 유도에 의해 보류 될 수 있습니다 :
-- base case
fmap id []
[] -- definition of fmap
id [] -- definition of id
-- inductive step
fmap id (x:xs)
id x : fmap id xs -- definition of fmap
x : fmap id xs -- definition of id
x : id xs -- by the inductive hypothesis
x : xs -- definition of id
id (x : xs) -- definition of id
비슷하게, 구성법 :
-- base case
(fmap f . fmap g) []
fmap f (fmap g []) -- definition of (.)
fmap f [] -- definition of fmap
[] -- definition of fmap
fmap (f . g) [] -- because [] = fmap f [], for all f
-- inductive step
(fmap f . fmap g) (x:xs)
fmap f (fmap g (x:xs)) -- definition of (.)
fmap f (g x : fmap g xs) -- definition of fmap
f (g x) : fmap f (fmap g xs) -- definition of fmap
(f . g) x : fmap f (fmap g xs) -- definition of (.)
(f . g) x : fmap (f . g) xs -- by the inductive hypothesis
fmap (f . g) xs -- definition of fmap
기능들
모든 Functor
가 컨테이너처럼 보이지는 않습니다. 함수의 Functor
인스턴스는 다른 함수의 반환 값에 함수를 적용합니다.
instance Functor ((->) r) where
fmap f g = \x -> f (g x)
이 정의는 fmap = (.)
와 같습니다. 따라서 fmap
함수 합성을 일반화합니다.
신원 확인 법칙을 한 번 더 확인하십시오.
fmap id g
\x -> id (g x) -- definition of fmap
\x -> g x -- definition of id
g -- eta-reduction
id g -- definition of id
및 구성법 :
(fmap f . fmap g) h
fmap f (fmap g h) -- definition of (.)
fmap f (\x -> g (h x)) -- definition of fmap
\y -> f ((\x -> g (h x)) y) -- definition of fmap
\y -> f (g (h y)) -- beta-reduction
\y -> (f . g) (h y) -- definition of (.)
fmap (f . g) h -- definition of fmap
펑터 및 법칙의 클래스 정의
class Functor f where
fmap :: (a -> b) -> f a -> f b
fmap
이 값의 함수를 문맥 f
의 값의 함수로 들어 올리는 것을 보는 한 가지 방법이 있습니다.
의 올바른 예 Functor
이는 컴파일러에 의해 적용되지 않습니다 불구하고, 펑터의 법칙을 만족해야합니다 :
fmap id = id -- identity
fmap f . fmap g = fmap (f . g) -- composition
<$>
라고 불리는 fmap
일반적으로 사용되는 중위 fmap
있습니다.
infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
Functor의 모든 요소를 단일 값으로 바꾸기
Data.Functor
모듈에는 펑터에 포함 된 모든 값을 무시하고 하나의 상수 값으로 대체하는 두 개의 결합 자, <$
및 $>
있습니다.
infixl 4 <$, $>
<$ :: Functor f => a -> f b -> f a
(<$) = fmap . const
$> :: Functor f => f a -> b -> f b
($>) = flip (<$)
void
는 계산의 반환 값을 무시합니다.
void :: Functor f => f a -> f ()
void = (() <$)
다항식 펑터
더 작은 것들로 큰 Functor
를 만드는 데 유용한 유형 Functor
있습니다. 이들은 Functor
예제 인스턴스로서 유용하며, 일반적인 펑터 (functor)의 큰 클래스를 나타내는 데 사용될 수 있기 때문에 generic 프로그래밍의 기술로 유용합니다.
신원 확인자
ID 펑 터는 단순히 인수를 마무리합니다. 그것은 SKI 미적분학에서 I
결합 자의 유형 수준 구현입니다.
newtype I a = I a
instance Functor I where
fmap f (I x) = I (f x)
I
의 이름으로, 찾을 수 있습니다 Identity
에 Data.Functor.Identity의
모듈 .
상수 펑터
상수 펑터는 상수 값만 포함하는 두 번째 인수를 무시합니다. 그것은 유형 수준의 const
인 SKI 계산법의 K
결합 자입니다.
newtype K c a = K c
참고 K ca
어떤 포함하지 않는 -values을; a
K ()
는 Proxy
와 동형이다. 이것은 K
의 fmap
구현이 전혀 매핑을하지 않는다는 것을 의미합니다!
instance Functor (K c) where
fmap _ (K c) = K c
K
는 그렇지 않으면 Data.Functor.Const
Const
알려져 있습니다.
이 예제의 나머지 펑터는 더 작은 펑터를 더 큰 펑터로 결합합니다.
펑터 제품
Functor 제품은 한 쌍의 Functor를 가져다가 포장합니다. 튜플과 비슷하지만, (,) :: * -> * -> *
types
*
, (:*:) :: (* -> *) -> (* -> *) -> (* -> *)
는 functors
* -> *
에서 작동합니다.
infixl 7 :*:
data (f :*: g) a = f a :*: g a
instance (Functor f, Functor g) => Functor (f :*: g) where
fmap f (fx :*: gy) = fmap f fx :*: fmap f gy
이 형식은 Data.Functor.Product
모듈 에서 Product
라는 Product
이름으로 찾을 수 있습니다.
펑터 제품
:*:
는 (,)
와 유사합니다 :+:
는 Either
의 Functor 레벨 아날로그입니다.
infixl 6 :+:
data (f :+: g) a = InL (f a) | InR (g a)
instance (Functor f, Functor g) => Functor (f :+: g) where
fmap f (InL fx) = InL (fmap f fx)
fmap f (InR gy) = InR (fmap f gy)
:+:
는 Data.Functor.Sum
모듈 에서 Sum
이라는 이름으로 찾을 수 있습니다.
펑터 구성
마지막으로, :.:
는 유형 수준 (.)
과 같이 작동하며 하나의 함수기 출력을 가져 와서 다른 함수기의 입력에 연결합니다.
infixr 9 :.:
newtype (f :.: g) a = Cmp (f (g a))
instance (Functor f, Functor g) => Functor (f :.: g) where
fmap f (Cmp fgx) = Cmp (fmap (fmap f) fgx)
Compose
유형은 Data.Functor.Compose
에서 찾을 수 있습니다.
제네릭 프로그래밍을위한 다항식 펑터
I
, K
, :*:
, :+:
and :.:
는 단순한 데이터 유형의 특정 클래스에 대한 빌딩 블록 키트로 생각할 수 있습니다. 키트는 고정 점 과 결합 할 때 특히 강력합니다. 이러한 결합 Functor
데이터 유형은 자동으로 Functor
인스턴스이기 때문입니다. 이 키트를 사용하여 템플릿 유형을 만들고 I
사용하여 재귀 적 포인트를 표시 한 다음 Fix
에 연결하여 재귀 스키마의 표준 동물원에서 사용할 수있는 유형을 얻습니다.
이름 | 데이터 유형 | 펑터 키트 사용 |
---|---|---|
쌍의 값 | data Pair a = Pair aa | type Pair = I :*: I |
2x2 격자 | type Grid a = Pair (Pair a) | type Grid = Pair :.: Pair |
자연수 | data Nat = Zero | Succ Nat | type Nat = Fix (K () :+: I) |
기울기 | data List a = Nil | Cons a (List a) | type List a = Fix (K () :+: K a :*: I) |
이진 나무 | data Tree a = Leaf | Node (Tree a) a (Tree a) | type Tree a = Fix (K () :+: I :*: K a :*: I) |
장미 나무 | data Rose a = Rose a (List (Rose a)) | type Rose a = Fix (K a :*: List :.: I) |
데이터 유형을 설계하는이 "키트"접근법은 generics-sop
과 같은 일반 프로그래밍 라이브러리의 기본 개념입니다. 아이디어는 위에 제시된 것과 같은 키트를 사용하여 일반 작업을 작성한 다음 유형 클래스를 사용하여 임의의 데이터 유형을 일반 표현과 변환하거나 일반 표현으로 변환하는 것입니다.
class Generic a where
type Rep a -- a generic representation built using a kit
to :: a -> Rep a
from :: Rep a -> a
카테고리 이론의 Functor
Functor는 범주 이론에서 범주 간 구조 보존지도 ( '동형태')로 정의됩니다. 특히 (모든) 객체가 객체에 매핑되고 (모든) 화살표가 화살표로 매핑되므로 범주 법칙이 유지됩니다.
객체가 하스켈 형식이고 모폴로지가 하스켈 함수 인 범주를 하스 (Hask )라고 합니다 . 그래서 Hask에 Hask에서 펑 터는 유형 유형의 매핑 및 기능에 대한 기능에서 매핑 구성 것이다.
이 범주 이론적 개념이 하스켈 프로그래밍 구성 요소 Functor
맺는 관계는 오히려 직접적입니다. 유형에서 유형으로의 매핑은 f :: * -> *
형식의 형식을 취하고 함수에서 함수로의 매핑은 fmap :: (a -> b) -> (fa -> fb)
. 그것들을 함께 수업에 넣고,
class Functor (f :: * -> *) where
fmap :: (a -> b) -> f a -> f b
fmap
은 함수 (morphism의 한 종류) :: a -> b
를 취하여 다른 함수 :: fa -> fb
매핑하는 연산입니다. Functor
인스턴스가 Hask 의 범주 구조를 유지하면서 실제로 수학 펑터라고 가정합니다 (프로그래머에게 맡깁니다) .
fmap (id {- :: a -> a -}) == id {- :: f a -> f a -}
fmap (h . g) == fmap h . fmap g
fmap
은 임의의 신원 화살표의 존재와 합성의 연관성을 보존하는 방식으로 함수 :: a -> b
를 Hask 의 하위 범주로 끌어 올립니다 .
Functor
클래스는 Hask에서 endo 펑터 만 인코딩합니다. 그러나 수학에서 펑터는 임의의 범주간에 매핑 할 수 있습니다. 이 개념을보다 충실하게 인코딩하면 다음과 같이 보입니다.
class Category c where
id :: c i i
(.) :: c j k -> c i j -> c i k
class (Category c1, Category c2) => CFunctor c1 c2 f where
cfmap :: c1 a b -> c2 (f a) (f b)
표준 Functor 클래스는 소스 및 대상 범주가 모두 Hask 인이 클래스의 특별한 경우입니다. 예를 들어,
instance Category (->) where -- Hask
id = \x -> x
f . g = \x -> f (g x)
instance CFunctor (->) (->) [] where
cfmap = fmap
펑 터 파생
DeriveFunctor
언어 확장을 통해 GHC는 Functor
인스턴스를 자동으로 생성 할 수 있습니다.
{-# LANGUAGE DeriveFunctor #-}
data List a = Nil | Cons a (List a) deriving Functor
-- instance Functor List where -- automatically defined
-- fmap f Nil = Nil
-- fmap f (Cons x xs) = Cons (f x) (fmap f xs)
map :: (a -> b) -> List a -> List b
map = fmap