Тип Haskell, представляющий подмножество другого типа

Question

Я думаю, что при заданных параметрах (-ях) указанного типа функция никогда не должна прерываться.

Но возьмите этот, казалось бы, безобидный код:

readInts :: String -> [Int] 
readInts = map read . words 

Он имеет тип подписи, который является слишком общим, на самом деле, она не будет выполнена для любой строки, не сочиненной разделенных пробелами целых чисел, его тип должен тогда:

readInts :: SpaceSeparatedIntegersString -> [Int] 

когда программа терпит неудачу, когда вы пытаетесь построить SpaceSeparatedIntegersString, что не уважает указанные критерии.

• Осуществляет идею SpaceSeparatedIntegersString разумную идею?

• Если это так, как я могу реализовать такой тип? (Я прошу только общую идею/tip/nudge в правильном направлении, а не полный код)

• Должен ли я просто признавать, что моя функция не будет выполнена, если форматирование String неверно (то есть мое заявление в начале из этого вопроса не так)?

• Должен ли я использовать предложение охраны в определении функции?

Answer 1

Ваша цель благородна, но требует очень точных типов. Зависимые типы, такие, которые доступны в Agda, Coq, Idris и других языках, могут достичь того, что вы предлагаете. Например. в Coq,

Definition SpaceSeparatedIntegersString: Type := 
    { s: string | spaceSeparatedIntegers s } . 
Definition spaceSeparatedIntegers (s: String): Prop := ... 

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

В Haskell чаще всего передается тип-тип выходного типа. Вместо того, чтобы тип входа сильнее, мы можем сделать тип выхода слабее:

readInts :: String -> Maybe [Int] 

Это не так точно, но может быть использован без необходимости доказывать.

В противном случае make SpaceSeparatedIntegersString будет непрозрачным, объявив его в модуле без экспорта его конструкторов значений.

module Foo(SpaceSeparatedIntegersString(), ...) 
data SpaceSeparatedIntegersString = S String  -- S is private 

Таким образом, пользователям модуля придется манипулировать ими только через функции, экспортируемые модулем. С некоторой осторожностью можно создать кучу (экспортированных) комбинаторов, которые гарантируют, что значения типа SpaceSeparatedIntegersString никогда не будут содержать недопустимые строки. Например,

combine :: SpaceSeparatedIntegersString 
     -> SpaceSeparatedIntegersString 
     -> SpaceSeparatedIntegersString 
combine (S x) (S y) = S (x ++ " " ++ y) 

Это не совсем просто - если вы хотите, чтобы позволить манипуляции вообще строки, вы, вероятно, в конечном итоге в возвращении Maybe ... в некоторых случаях.

Answer 2

Возможно, вы не должны применять SpaceSeparatedIntegerString. Если бы вы сделали абстрактный тип данных, это было бы самой простой задачей. Вы не должны соглашаться с тем, что ваша функция должна потерпеть неудачу, по крайней мере, не в смысле «сбой шаблона». Вы должны сделать функцию, которая возвращает что-то вроде Maybe [Int].

Причина, по которой вы не должны реализовывать SpaceSeparatedIntegerString, скорее всего, вызовет проблему в другом месте. Вы, вероятно, получаете String s от некоторого ввода, поэтому где-то вам нужна функция String -> SpaceSeparatedIntegerString, и это может сработать так же хорошо. В какой-то момент вам нужно перейти от менее структурированных к более структурированным данным, если только ваши значения не будут полностью статически заданы.

Точка идет от менее структурированных данных до более структурированных данных (или менее типизированных данных для более типизированных данных) практически всегда будет частичной операцией. Действительно, синтаксический анализ - это процесс превращения менее структурированных данных в более структурированные данные. То, что вы должно, действительно, в соответствии с вашим принципом, практично reify восстановленная структура в систему типов. Таким образом, isValidUri :: String -> Bool является плохим, как и makeUri :: String -> Maybe String, но makeUri :: String -> Maybe Uri, где Uri - это тип, который может представлять собой действительные URI.

Answer 3

Нет, это не разумная идея в этом случае. Подход, предложенный в Ian Henry's comment с использованием Maybe, является одним из нескольких разумных. Причина, по которой ваша идея нечувствительна в этом контексте, заключается в том, что вся цель такой функции, как readInts, заключается в обработке ввода от пользователя, файла, HTTP-запроса и т. Д., Что может быть не. Система типов не может помочь вам, если вы спросите у пользователя, сколько автомобилей они хотят купить, и они отвечают изображением котенка. Дерек Элкинс объясняет это лучше. Типичный подход на основе chi отлично подходит для некоторых других ситуаций, как только вход полностью подтвержден.