Сопоставление с образцом в определении fromJust

Question

Функция fromJust в Data.Maybe определяется следующим образом:

fromJust          :: Maybe a -> a
fromJust Nothing  = error "Maybe.fromJust: Nothing"
fromJust (Just x) = x

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

Не могли бы вы уточнить мою ошибку в рассуждениях? Спасибо.

Edit:

Пример: Предположим, у меня есть файл с миллионом чисел типа Int на строку, и вам нужны эти числа (как Int, а не String) в моей программе для других вещей.

import qualified Data.ByteString.Lazy.Char8 as L

readInt = fst . fromJust . L.readInt
-- more stuff

С приведенным выше определением fromJust Мне нужно больше времени, чтобы прочитать цифры, не так ли?

Answer 1

Я думаю, что этот вопрос о производительности. Хотя семантически сопоставление с образцом проверяется сверху вниз, большинство компиляторов Haskell оптимизируют сопоставление конструкторов ADT с эквивалентом оператора C switch.

Вы можете думать, что представление данных для ADT имеет «тег», который говорит, с каким конструктором он был сделан, вместе с указателем для каждого аргумента. Так, например, Nothing может быть представлено как 0 (null), а Just 42 представлено как 1 (pointer to 42).

Тогда в такой функции:

squash :: Maybe (Maybe Int) -> Int
squash (Just Nothing) = 0
squash Nothing = 0
squash (Just (Just x)) = x

Компилятор установит дерево решений:

squash x = 
   check tag of x:
       0 -> 0
       1 y -> check tag of y:
           0 -> 0
           1 z -> z

Там, где каждый тег вычисляется с помощью таблицы переходов или чего-то еще, так что проверять 0 как 1 не дороже. Обратите внимание, что это одно и то же дерево решений будет принято независимо от того, каков первоначальный порядок шаблонов в нашем определении.

Тем не менее, при использовании защиты вместо сопоставления в конструкторе, шаблоны, скорее всего, проверяются сверху вниз (для оптимизации этого компилятор должен быть очень умным). Так что, если мы написали fromJust таким загадочным образом:

fromJust x
    | isNothing x = error "fromJust: Nothing"
    | isJust x = case x of { Just y -> y }

Тогда это, вероятно, будет проверять каждый конструктор по очереди, и мы могли бы оптимизировать, переключая порядок дел. К счастью, писать так, как это важно, громоздко: -).

Answer 2

Здесь необходимо реализовать две важные вещи: во-первых, компилятор Haskell полностью осознает, что любое значение может быть только Nothing или Just x. Поэтому он будет когда-либо проверять только один из них Во-вторых, GHC использует теги указателей, которые позволяют очень быстро различать указатели, указывающие на различные конструкторы ( детали ).

В результате GHC генерирует довольно хороший код для сопоставления с образцом. Вот как выглядит код возврата fromJust, взятый непосредственно из дампа сборки:

        andq $7,%rax
        cmpq $2,%rax
        jae .LcO4

Принимает возвращаемое значение, затем извлекает тег, используя операцию битовой маски (7 = 111 в двоичном виде). Если этот тег равен 2, то код знает, что он указывает на конструктор Just x. Поэтому он переходит к соответствующему коду. В противном случае он просто переходит к коду, имеющему дело с Nothing.

Я думаю, это можно было бы еще больше оптимизировать, если учесть, что в программе имеется только одно Nothing замыкание. Поэтому вы можете заменить это сравнением с одним адресом, сохранив операции маскирования битов и даже регистр в реальном коде. Не уверен, почему GHC не делает этого.

Answer 3

Нечто, совпадающее с Nothing, не может совпадать с Just. Так что оба заказа работают.

Если вы передаете Just 5 через fromJust, Just 5 не соответствует Nothing. Но Just 5 соответствует Just x.

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