Сортировать список пар Int по разности значений (a, b) - PullRequest
Новая
       38

Сортировать список пар Int по разности значений (a, b)

0 голосов
/ 28 мая 2018

Как мне отсортировать list из Int пар по разности значений |first - second| в порядке возрастания?

Для вычисления разницы я написал этот фрагмент кода: 

ab :: (Int, Int) -> Int
ab (x, y) = if x - y >= 0 then (x - y)
            else (x - y) * (-1)

Я хотел использовать quicksort для значений, которые я получаю: 

sort :: [(Int,Int)] -> [(Int,Int)]
sort [] = []
sort (x:xs) = sort smallerOrEqual ++ [x] ++ sort larger
          where smallerOrEqual = [a | a <- xs, a <= x]
                larger = [a | a <- xs, a > x]

Проблема в том, как мне встроить мою ab функцию в the функцию сортировки?Я пробовал несколько способов, но всегда получал ошибки компилятора.

Ответы [ 2 ]

0 голосов
/ 28 мая 2018

Хотя sortBy общеизвестно, оно в основном сопровождается comparing.Вы можете использовать sortOn вместо этого.Преимущество sortOn состоит в том, что он использует преобразование Шварца, то есть он вычисляет разность только для каждого элемента. 

--Prelude Data.List> :t sortOn
--sortOn :: Ord b => (a -> b) -> [a] -> [a]

import Data.List(sortOn)
sort = sortOn (abs . uncurry (-))

Но если вы действительно хотите использовать свою исходную сортировку, шаблон соответствует парам: 

sort ((x,x'):xs) = [ (a,a') | (a,a') <- xs, -- ... your homework here

Позже я расширяю домашнюю часть, чтобы дать ей полный ответ.

0 голосов
/ 28 мая 2018

Давайте сделаем это только со стандартными библиотечными функциями!

Прежде всего, существует общая версия функции сортировки с именем sortBy (я покажу типы соответствующих функций по мере использования, используяБлестящая команда GHCi :t): 

ghci> import Data.List
ghci> :t sortBy
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

Первый параметр sortBy предполагает, что для сравнения элементов нам необходим сортировочный предикат - функция, которая принимает два элемента списка иговорит, если первый больше.Во многих случаях, включая ваш, вам не нужно определять такую ​​функцию самостоятельно.Вместо этого вы можете использовать функцию, которая « измеряет », насколько важен элемент списка.Например, у вас есть элемент списка (x,y), и его мера равна |x-y| - это именно ваша ab функция, но помните, что мы хотим, чтобы она определялась с помощью стандартных.

На данный момент,у нас есть две задачи: 1) определить функцию измерения типа (Int, Int) -> Int;2) научиться превращать его в предикат сортировки.Я сказал, что последнее тривиально, так как это можно сделать с помощью стандартной функции comparing: 

ghci> import Data.Ord
ghci> :t comparing
comparing :: Ord a => (b -> a) -> b -> b -> Ordering

Так что я предлагаю, чтобы comparing ab идеально подходило для первого аргумента.sortBy.Не будем переходить к другой задаче: определение ab с помощью стандартных функций.

Рассмотрим тип - функции: 

ghci> :t (-)
(-) :: Num a => a -> a -> a

Если вы замените Int на a (¹) вы получаете почти тот тип, который хотите иметь, например Int -> Int -> Int.Здесь мы выполняем очень частую задачу по превращению функции из двух аргументов ((-)) в функцию, действующую на парах.К счастью, для этого есть стандартная функция, а именно: uncurry: 

ghci> :t uncurry (-)
uncurry (-) :: Num c => (c, c) -> c

Вот что нам нужно!Теперь нам просто нужно передать это с помощью функции abs, которая вычисляет |·|, и мы в порядке.Мы составляем функции с помощью ..В результате получится следующее решение: 

import Data.List (sortBy)
import Data.Ord  (comparing)

sortAbsPairs :: [(Int,Int)] -> [(Int,Int)]
sortAbsPairs = sortBy (comparing $ abs . uncurry (-))

Вы можете попробовать его в GHCi, если вы сохранили его в sort.hs: 

ghci>:l sort.hs
Ok, one module loaded.
ghci> sortAbsPairs [(8,20), (5, 10), (1,2)]
    [(1, 2), (5, 10), (8, 20)]

(¹) Вы можете спроситьGHCi для замены типов на параметры типа функций путем установки расширения языка с именем TypeApplications: 

ghci> :set -XTypeApplications
ghci> :t (-) @Int
(-) @Int :: Int -> Int -> Int
...