Haskell Language
펑터

소개

비고

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 에 연결하여 재귀 스키마의 표준 동물원에서 사용할 수있는 유형을 얻습니다.

데이터 유형을 설계하는이 "키트"접근법은 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