Эквивалентные функции, дающие разные результаты интерпретатора - PullRequest
Новая
       24

Эквивалентные функции, дающие разные результаты интерпретатора

6 голосов
/ 17 января 2012

Предыстория: я занимаюсь расследованием анонимной рекурсии, и я беру на себя задачу реализации прелюдии без использования какой-либо именованной рекурсии просто для того, чтобы все это было в моей памяти.Я еще не совсем там, и по пути я столкнулся с чем-то не связанным, но все еще интересным. 

map1     = \f -> \x -> if (tail x) == [] 
                       then [f (head x)] 
                       else f (head x) : (map1 f (tail x))

map2 f x =             if (tail x) == [] 
                       then [f (head x)] 
                       else f (head x) : (map2 f (tail x))

map3 f (x:xs) = if xs == [] then [f x] else f x : (map3 f xs)

map4 f (x:[]) = [f x]
map4 f (x:xs) =  f x : map4 f xs

GHC жалуется на первое, хорошо со вторым, третьим и четвертымЯ просто хочу показать, как они могут быть реализованы по-разному. 

*Main> map1 (*2) [1..10]

<interactive>:1:15:
    No instance for (Num ())
      arising from the literal `10'
    Possible fix: add an instance declaration for (Num ())
    In the expression: 10
    In the second argument of `map1', namely `[1 .. 10]'
    In the expression: map1 (* 2) [1 .. 10]
*Main> map2 (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> map3 (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> map4 (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]

Если я добавлю сигнатуру типа в map1, все будет хорошо. 

map1 :: Eq a => (a -> b) -> [a] -> [b]

Первые две функции кажутся в значительной степениТо же самое для меня, поэтому я полагаю, что мой вопрос просто «Что здесь происходит?»

Ответы [ 2 ]

12 голосов
/ 17 января 2012

Вас укусило ограничение мономорфизма . Все, что записано как foo = ... - это означает, что в определении нет аргументов и не указан явный тип - должно иметь неуниверсальный тип в соответствии с этим ограничением. Универсальный тип в этом случае, как вы сказали, должен был быть Eq a => (a -> b) -> [a] -> [b], но, поскольку применяется ограничение мономорфизма, оба значения a и b заменяются на (), самый простой тип, который можно вывести для доступные переменные типа.

6 голосов
/ 17 января 2012

Но, если вы используете неограниченный null вместо (== []), 

Prelude> let map0 = \f -> \x -> if null (tail x) then [f (head x)] else f (head x) : map0 f (tail x)
Prelude> :t map0
map0 :: (a -> t) -> [a] -> [t]
Prelude> map (*2) [1 .. 10]
[2,4,6,8,10,12,14,16,18,20]

работает без аргументов и подписи. Только переменные ограниченного типа подпадают под ограничение мономорфизма .

И если вы поместите определение map1 в файл и попытаетесь скомпилировать его или загрузить в ghci, 

Ambiguous type variable `a0' in the constraint:
  (Eq a0) arising from a use of `=='
Possible cause: the monomorphism restriction applied to the following:
  map1 :: forall t. (a0 -> t) -> [a0] -> [t] (bound at Maps.hs:3:1)
Probable fix: give these definition(s) an explicit type signature
              or use -XNoMonomorphismRestriction
In the expression: (tail x) == []
In the expression:
  if (tail x) == [] then
      [f (head x)]
  else
      f (head x) : (map1 f (tail x))
In the expression:
  \ x
    -> if (tail x) == [] then
           [f (head x)]
       else
           f (head x) : (map1 f (tail x))

ghci жаловался только так, как он, потому что он использует ExtendedDefaultRules, иначе вы бы получили понятное сообщение об ошибке.

...