Вопрос по haskell – Почему определение функций для всех типов одновременно не разрешено в Haskell?

23

Это, наверное, очень простой вопрос, но ...

Функция, которая определена как, скажем,

foo :: a -> Integer

обозначает функцию изany введите целое число. Если это так, то в теории можно определить его для любого типа, например

foo 1 = 10
foo 5.3 = 100
foo (x:xs) = -1
foo  _     = 0

Но Haskell позволяет только общее определение, какfoo a = 0.

И даже если вы ограничиваетеa быть одним из определенного класса типов, например экземпляра класса типов Show:

foo :: (Show a) => a -> Integer

Вы все еще не можете сделать что-то вроде

foo "hello" = 10
foo   _     = 0

даже если"hello" :: [Char] является примеромShow

Почему существует такое ограничение?

Ваш Ответ

5   ответов
20

a -> Integer допускается только одно поведение - возвращать постоянное целое число. Зачем? Потому что вы не знаете, какой типa является. Без заданных ограничений это может быть абсолютно что угодно, а поскольку Haskell статически типизирован, вам нужно разрешить все, что связано с типами во время компиляции. Во время выполнения информация о типе больше не существует и, следовательно, с ней невозможно ознакомиться - все варианты выбора используемых функций уже сделаны.

Наиболее близким Haskell к такому поведению является использование классов типов - если вы создали класс типов, называемыйFoo с одной функцией:

class Foo a where
    foo :: a -> Integer

Тогда вы можете определить экземпляры этого для разных типов

instance Foo [a] where
    foo [] = 0
    foo (x:xs) = 1 + foo xs

instance Foo Float where
    foo 5.2 = 10
    foo _ = 100

Тогда, пока вы можете гарантировать какой-то параметрx этоFoo ты можешь позвонитьfoo в теме. Это все еще нужно, хотя - тогда вы не можете написать функцию

bar :: a -> Integer
bar x = 1 + foo x

Поскольку компилятор не знает, чтоa является примеромFoo, Вы должны сказать это, или опустить сигнатуру типа и позволить ей понять это для себя.

bar :: Foo a => a -> Integer
bar x = 1 + foo x

Haskell может работать только с таким количеством информации, которое есть у компилятора о типе чего-либо. Это может показаться ограничительным, но на практике классы типов и параметрический полиморфизм настолько мощны, что я никогда не пропускаю динамическую типизацию. Фактически, меня обычно раздражает динамическая типизация, потому что я никогда не совсем уверен, что на самом деле есть.

32

и на самом деле она очень важна. Это сводится к собственности, известной какparametricity в теории языка программирования. Грубо говоря, это означает, что оценка никогда не должна зависеть от типов, которые являются переменными во время компиляции. Вы не можете посмотреть на значение, где вы не знаете его конкретный тип статически.

Почему это хорошо? Это дает гораздо более сильные инварианты о программах. Например, по одному только типу вы знаете, чтоa -> a должна быть функция идентичности (или расходится). Подобные «свободные теоремы» применяются ко многим другим полиморфным функциям. Параметричность также является основой для более продвинутых методов абстракции на основе типов. Например, типST s a в Haskell (государственная монада) и тип соответствующегоrunST функция, положиться наs будучи параметрическим. Это гарантирует, что у запущенной функции нет возможности связываться с внутренним представлением состояния.

Это также важно для эффективной реализации. Программа не должна передавать дорогостоящую информацию о типе во время выполнения (type erasure), и компилятор может выбирать перекрывающиеся представления для разных типов. Как пример последнего, 0 и False и () и [] все представлены 0 во время выполнения. Это было бы невозможно, если бы была разрешена такая функция, как ваша.

This paper может быть актуальным.
21

известную как «стирание типа»: типы не имеют вычислительного значения, поэтому код, который вы генерируете, не должен их отслеживать. Это значительное благо для производительности.

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

f () = "foo"
f [] = "bar"

тогда это свойство не будет правдой: поведениеf будет действительно зависеть от типа его первого аргумента.

Конечно, есть языки, которые допускают подобные вещи, особенно в языках с типизированной зависимостью, где типы вообще не могут быть стерты в любом случае.

@ChrisTaylor: Хорошо, у меня был такой же опыт. Думая об этом немного, я подозреваю, что причина в подтипировании. Почти каждый раз, когда я хотел / нужно было использоватьinstanceof было из-за подтипа. Кроме того, типы сумм позволяют вам писать код, который работает в основном так, за исключением того, что вам нужно обернуть все в ADT. Это похоже на использованиеinstanceof за исключением всех явных возможностей.
Это интересно. Когда я программировал на Java, меня часто раздражало стирание типов. Это означало, чтоList<T> не знал, чтоT был во время выполнения, поэтому вы не можете написать код, подобныйif (x instanceOf T) {...}, Но я никогда даже не замечал, что Haskell использует стирание типов. Интересно, почему это так.
Частично это происходит из-за того, что у Haskell нет «подтипов». Вы почти всегда знаетеexact тип каждой переменной во время компиляции, тогда как в Java вы можете получить разные реализации одного и того же интерфейса. В редких исключениях, таких как экзистенциально количественные типы, выdeliberately выбросить эту информацию о типе, так что вы должны знать, что в будущем эта информация вам не понадобится.
Теоретически возможно просто нарушить определениеf до всех возможных типов во время компиляции, но для существования экзистенциальных типов.
@ChrisTaylor Возможно, потому что GHC использует стирание типов в качестве оптимизации, а Java использует стирание типов в качестве гарантии.typeOf x в Haskell назовут правильный экземплярTypeable для х. Хотя за общие функции приходится платить ... они, безусловно, не бесплатны. Общий налог будет выплачен во время компиляции, выполнения или обоих.
12

Хаскелл может это сделать! (хотя это обычно используется только в очень определенных обстоятельствах)

{-# LANGUAGE ScopedTypeVariables, NoMonomorphismRestriction #-}

import Data.Generics

q1 :: Typeable a => a -> Int
q1 = mkQ 0 (\s -> if s == "aString" then 100 else 0)

q2 :: Typeable a => a -> Int
q2 = extQ q1 (\(f :: Float) -> round f)

Загрузите это и поэкспериментируйте с этим:

Prelude Data.Generics> q2 "foo"
0
Prelude Data.Generics> q2 "aString"
100
Prelude Data.Generics> q2 (10.1 :: Float)
10

Это не обязательно вступает в противоречие с ответами о том, что типы утверждений не имеют вычислительного значения. Это потому, что эти примеры требуютTypeable ограничение, которое преобразует типы в значения данных, которые доступны во время выполнения.

Большинство так называемых обобщенных функций (например, SYB) полагаются наTypeable илиData ограничение. Некоторые пакеты вводят свои собственные альтернативные функции, которые служат по существу той же цели. Без чего-либо подобного этим классам это невозможно сделать.

16

a -> Integer на самом деле не означает "функцию отany введите вInteger& Quot; как вы это описываете. Когда определение или выражение имеет типa -> Integer, это означает, что для любого типаTможноspecialize или жеinstantiate это определение или выражение в функцию типаT -> Integer.

Слегка переключая нотацию, можно думать об этом так:foo :: forall a. a -> Integer действительно функцияtwo аргументы: типa и значение этого типаa, Или, с точки зрения карри,foo :: forall a. a -> Integer это функция, которая принимает типT в качестве аргумента, и производит специализированную функцию типаT -> Integer для этогоT, Используя функцию тождества в качестве примера (функция, которая создает свой аргумент в качестве результата), мы можем продемонстрировать это следующим образом:

-- | The polymorphic identity function (not valid Haskell!)
id :: forall a. a -> a
id = \t -> \(x :: t) -> x

Эта идея реализации полиморфизма как аргумента типа для полиморфной функции исходит из математической структуры, называемойСистема F, который Хаскель фактически использует в качестве одного из своих теоретических источников. Однако Haskell полностью скрывает идею передачи параметров типа в качестве аргументов функциям.

+1 в то время как другие ответы говорят кое-что замечательное, я считаю, что это объяснение неявной передачи типов - Правильный ответ. Рассмотрим разницу в типизированной ракетке между типами(Any -> Integer) а также(All (A) (A -> Integer)), Поскольку в Haskell нет подтипов, первое невозможно.
+1, но я хотел бы добавить одну вещь: универсальное количественное определение можно рассматривать как функцию, принимающую дополнительный аргумент типа, только когда множество всех типов (* в Haskell) является абстрактным (то есть вы не можете сопоставить шаблон с ним). Если бы это было не так, вы вполне могли бы иметь функцию\(t :: *) -> case t of Int -> ..., В качестве примераid функция в Агде имеет тип(A : Set) → A → Aпотому что нам не разрешеноSet, id должен иметь формуid A x = x.

Похожие вопросы