Haskell: Полиморфные функции объяснения

Question

Так я даюсь это

intCMP :: Int -> Int -> Ordering 
intCMP a b | a == b = EQ 
    | a < b = LT 
    | otherwise = GT 

intCMPRev :: Int -> Int -> Ordering 
intCMPRev a b | a == b = EQ 
    | a < b = GT 
     | otherwise = LT 

floatCMP :: Float -> Float -> Ordering 
floatCMP a b | a == b = EQ 
     | a < b = LT 
     | otherwise = GT 

Мне нужно написать эту функцию

sort3 :: Ord a => (a -> a-> Ordering) -> [a] -> [a] 
sort3 cmp xs = 

Какой будет сортировать 3 или меньше элементов по сравнению. Нет рекурсии. Мне было интересно, как это работает, если передать intCMP. Зачем вы передавали это в функцию сортировки? Выполняет ли это назначение при сортировке и возврате отсортированного списка? Я не совсем уверен, как делать подобные сравнения вручную без какого-либо рекурсивного вызова, поэтому я просто пытаюсь понять это лучше.

Я думал делать 3 сравнений, а затем переместить элемент в определенную позицию в списке, но я действительно не знаю, как я мог даже сделать это в Haskell. Любые подсказки о том, как начать это, были бы замечательными. Может быть, какой-то образец?

Спасибо.

Answer 1

Частичный ответ на первую часть вопроса:

Переходя в intCMP к sort3 позволяет контролировать, как сортировка делается. Предположительно, sort3 intCMP [7,3,6] вернется [3,6,7], в то время как sort3 intCMPRev [7,3,6] вернется [7,6,3]. Вы можете даже создавать свои собственные странные функции сортировки, как сначала все четные числа, а затем все нечетные в порядке убывания, например, так:

intCMPWeird :: Int -> Int -> Ordering 
intCMPWeird a b 
    | even a && even b = intCMP a b -- even numbers compare as usual 
    | odd a && odd b = intCMPRev a b -- odd numbers compare in reverse order 
    | even a && odd b = LT -- evens are all 'smaller' than odds 
    | odd a && even b = GT -- odds are all 'greater' than evens 

Используя это, sort3 intCMPWeird [7,3,6] должен дать [6,7,3].

Что происходит во время проверки типов, когда вы проходите один из intCMP... функций в sort3 есть (в очень небольшом словах), что компилятор пытается соответствовать типу sort3 «s первого аргумента (a -> a -> Ordering) с типом поставляемым значением (Int -> Int -> Ordering) и удается сделать это, сделав a равным Int. Затем необходимо проверить, выполнено ли ограничение Ord a для Int, которое работает! Наконец, компилятор может выяснить, что тип sort3 intCMP - [Int] -> [Int]. Аналогичным образом, sort3 floatCMP имеет тип [Float] -> [Float].

Я не уверен на 100%, почему ограничение Ord относится к типу sort3, так как вы можете получить необходимую информацию из переданной функции сравнения - вы уверены, что правильно набрали?

EDIT: Подсказка о том, как использовать где положение, чтобы получить читаемое определение, вы должны заполнить некоторые биты и добавить еще несколько статей:

sort3 cmp [x,y,z] 
    | x <= y && somethingElse1 = listWithXyzInSomeOrder1 
    | x <= z && somethingElse2 = listWithXyzInSomeOrder2 
     where a <= b = cmp a b /= GT 

Answer 2

Вы не пишете полиморфные функции (которая по определению является функция, которая принимает более одного типа). Написать один первый:

cmp :: Ord a => a -> a -> Ordering 
cmp x y = 
    | x == y = EQ 
    | x < y = LT 
    | otherwise = GT 

Вы написали бы над таким образом функциональность, которая сравнивает элементы в этом роде, не должны быть частью рода. Сортировка списка по своей природе рекурсивна: по крайней мере, если длина не определена. Для этого просто напишите сортировку, которая может использовать ваше пользовательское сравнение, вот quick sort, хотя вы могли бы написать другой тип сортировки.

sort3 :: (Ord a) => [a] -> [a] 
sort3 [] = [] 
sort3 (x:xs) = 
    let smallerSorted = filter (<=) 
     biggerSorted = filter(>) 
    in smallerSorted ++ [x] ++ biggerSorted 

Answer 3

Вот подсказка:

• Если у вас есть пустой список, ясно результат сортировки будет пустой список.
• Аналогично, список с одним элементом также уже отсортирован.
• Если у вас есть список, состоящие из 2-элементного, есть только два возможная упорядоченность, следовательно, только 2 возможного значения возврата из вашей функции.
• Если у вас есть список из 3-элементный, существует 6 возможных порядков (первый элемент может быть 1 из 3 входных элементов, следующий элемент может быть 1 из 2 оставшихся, оставив только один выбор для последнего элемента). Вы можете легко записать 6 разных условий, заставив вас вернуть 1 из 6 возможных списков из трех элементов.