Вручную вывести тип развлечения xss = \f -> let ope x y = x . ф . y в папке r1 открыть xss

Я пытаюсь вручную вывести тип fun xss = \f -> let ope x y = x . f . y in foldr1 ope xss

ф. г

y :: t1 -- First occurrence
f :: t2 -- First occurrence

(.) (b1 -> c1) -> (a1 -> b1) -> a1 -> c1 -- (.) definition

t1 ~ a1 -> b1 -- y unified with (a1 -> b1)
t2 ~ b1 -> c1 -- y unified with (b1 -> c1)

y :: a1 -> b1
f :: b1 -> c1
---
f . y :: a1 -> c1 -- Cancellation rule

\f -> пусть ope x y = x . ф . г

(.) (b2 -> c2) -> (a2 -> b2) -> a2 -> c2 -- (.) definition

x :: t3 -- First occurrence

t3 ~ b2 -> c2 -- x unified with (b2 -> c2)
a1 -> c1 ~ a2 -> b2 -- f . y unified with (a2 -> b2)

a1 ~ a2
c1 ~ b2

y :: a2 -> b1 -- Substituing a1 by a2
f :: b1 -> b2 -- Substituing c1 by b2
x :: b2 -> c2 -- Substituing t3 by b2 -> c2
---
x . f . y :: a2 -> c2 -- Cancellation rule
(\f -> let ope x y :: x . f . y) 
          :: (b2 -> c2) -> (a2 -> b1) -> (b1 -> b2) -> a2 -> c2 -- Adding f

foldr1 открывает xss

foldr1 :: (a -> a -> a) -> [a] -> a -- foldr1 definition

xss ~ t4 -- First occurrence

Затем a ~ (b2 -> c2), a ~ (a2 -> b1), a ~ (b1 -> b2) and t4 ~ [a], что кажется ошибкой.

Любая помощь?

Спасибо,
Себастьян.


types haskell unification
person Fof    schedule 09.05.2014    source источник
comment
Ваша проблема в последнем пассаже во втором блоке. На самом деле вам нужно знать тип ope, который затем можно унифицировать с типом foldr1. Я предполагаю, что странный способ, которым Вы это написали, с посторонними \f -> и let, приводит к путанице.   -  person duplode    schedule 09.05.2014
comment
проблема в том, что ваше второе выражение, \f -> let ope x y = x . f . y, является недопустимым выражением. Просто как тот. Недопустимые выражения не имеют типов. Правильный разбор (\f -> (let {ope x y = x . f . y} in (foldr1 ope xss))).   -  person Will Ness    schedule 10.05.2014

Ответы (2)


arrow_upward
1
arrow_downward

Для начала с функцией

fun xss = \f -> let ope x y = x . f . y in foldr1 ope xss

Я перепишу это как

fun xss f = foldr1 ope xss
    where ope x y = x . f . y

Итак, мы начинаем с foldr1:

foldr1 :: (a -> a -> a) -> [a] -> a

Так что мы можем сломаться

foldrl1
    ope    -- (a -> a -> a)
    xss    -- [a]

Итак, ope :: a -> a -> a, это действительно полезно знать, так как это упрощает типы x и y, полностью ограничивая их a, или, другими словами, они оба имеют один и тот же тип. Поскольку они обе являются функциями (как того требует .), вместо того, чтобы долго унифицировать их типы, я просто скажу, что x, y :: b -> c

ope x y =    x     .    f     .    y
--        (b -> c) . (s -> t) . (b -> c)

Сейчас я оставил тип f неизвестным, за исключением указания, что это должна быть функция. Поскольку мы знаем, что x и y имеют один и тот же тип, теперь мы можем сказать, что тип вывода y совпадает с типом ввода f, поэтому тип вывода s ~ c и f должен быть таким же, как тип ввода x, поэтому t ~ b, поэтому мы получить

ope x y =    x     .    f     .    y
--        (b -> c) . (c -> b) . (b -> c)

Итак, теперь мы можем заполнить подпись fun. Мы уже знаем тип xss, это a ~ b -> c, а поскольку тип вывода foldr1 также a, мы получаем

 fun :: [b -> c] -> (c -> b) -> (b -> c)

И действительно, это тип, который дает нам GHCi

person bheklilr    schedule 09.05.2014

arrow_upward
1
arrow_downward

Вот вывод.

fun xss = \f -> let ope x y = x . f . y in foldr1 ope xss

fun xss f = foldr1 ope xss
   where
      ope x y = x . f . y                                      y :: a -> b
              =     y   >>>   f   >>>   x                      f :: b -> c
                  a -> b    b -> c    c -> d                   x :: c -> d
              ::  a  ------------------->  d

ope          x         y    ::  a->d
ope    ::  (c->d) -> (a->b) -> (a->d)

foldr1 :: (  a1   ->   a1   ->   a1  ) -> [ a1 ] ->   a1       c ~ a, d ~ b
          ((a->b) -> (a->b) -> (a->b)) -> [a->b] -> (a->b)     a1 ~ a->b
foldr1                ope                  xss   :: (a->b)

fun      xss       f    ::  a->b
fun :: [a->b] -> (b->a) -> (a->b)

Композиция функций ассоциативна: f . (g . h) =~= (f . g) . h. Вот почему выражение f . g . h правильно построено.

Точно так же, как (.) :: (b->c) -> (a->b) -> (a->c) создает цепочку из двух функций, питающих одну от другой, выражение f . g . h создает цепочку из трех функций, каждая из которых принимает в качестве входных данных выходные данные своей предшественницы.

Иногда проще использовать двоюродного брата (.), >>>, который просто меняет порядок аргументов:

f . g === g >>> f

Он определен в Control.Category.

person Will Ness    schedule 09.05.2014