사용자 정의 정렬 하스켈

Question

에서

두 번째 업데이트 :

드디어 zurgl의 제안을 따라 반복적으로 순회 및 그룹 something을 썼다. 도움을 주려고하는 모든 사람들에게 감사드립니다!

먼저 업데이트 : 정렬 기능을 할 수있는 희망하지만, 따를 것입니다 그룹화 (그룹의 수를 최소화)를 최적화하기 위해 의미되었다에 대해 확신 할 수 없었다 무엇

. 은 "정렬"후에, 제 2 예의

f xs = 
    foldr (\a@(y,x) ((b@(y',x'):xs):bs) -> if (y == y' && abs (x-x') == 1) || 
              (x == x' && abs (y-y') == 1) 
              then (a:b:xs):bs 
              else [a]:(b:xs):bs) 
              [[last xs]] (init xs) 

출력 : 그룹핑은 인접한 수평 또는 수직이다 튜플 수집

*Main> f [(0,1),(1,1),(2,1),(2,2),(2,3),(1,3),(0,3),(4,1),(4,2)] 
[[(0,1),(1,1),(2,1),(2,2),(2,3),(1,3),(0,3)],[(4,1),(4,2)]] 

--end

updates--의 나는 정렬 함수를 고민하는 데 어려움을 겪고 있으며, 누군가가 그것을 구현하는 방법에 대한 생각을 갖고 있거나 커스텀 정렬보다 더 많은 것이 필요할 지 모른다 고 생각하기를 바라고있다. 나는 sortBy와 함께 놀고 자 노력했지만 많은 진전을 보이지는 않는다.

어떻게이에서받을 수 있나요 :

[(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)] 

이에 '및 X X' y를 y를 둘 사이에 0 또는 1의

[(0,1),(1,1),(2,0),(2,1),(0,3),(1,3),(2,3),(4,1),(4,2)] 

차이 기본이 될 것이다. 말이 돼?

두 번째 예 :

[(0,1),(0,3),(1,1),(1,3),(2,1),(2,2),(2,3),(4,1),(4,2)] 
=> 
[(0,1),(1,1),(2,1),(2,2),(2,3),(1,3),(0,3),(4,1),(4,2)] 

Answer 1

내 하스켈이 매우 녹슨하지만이 덜합니다 (

subsortGT a, b 
    | a <= b = GT 
    | a > b = LT 

sortGT (a1, b1) (a2, b2) 
    | a1 + b1 < a2 + b2 = GT 
    | a1 + b1 > a2 + b2 = LT 
    | a1 + b1 == a2 + b2= subsortGT a1 a2 

sortBy sortGT [(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)] 

Answer 2

이

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

customSort = sortBy (comparing (\(x,y) -> (x+y, abs (x-y)))) 

또는 화살표 무료 포인트

을 정렬 튜플을 활용하여 포인트를 수행해야합니다)

import Control.Arrow ((&&&)) 

customSort = sortBy (comparing $ uncurry ((uncurry (&&&) .) ((+) &&& ((abs .) . subtract)))) 

Answer 3

사용자 지정 데이터 형식 및 지정된 순서를 정의하려고합니다.
나는 당신에게이 같은 제안

data MPair a = MPair a a deriving (Show) 

-- some helper to test 
toTuple (MPair x y) = (x, y) 
fromX x = MPair x x 

instance (Eq a) => Eq (MPair a) where 
    (MPair a b) == (MPair c d) = (a == c) && (b == d) 

-- This is not exactly the ordering you are looking for 
-- But at this stage it should no be a pain to define 
-- the required ordering, you just have to implement it below 
instance (Ord a) => Ord (MPair a) where 
    compare p@(MPair a b) q@(MPair c d) 
      | p == q = EQ 
      | otherwise = case (compare a c, compare b d) of 
          (LT, _) -> LT 
          (_, LT) -> LT 
          _  -> GT 

-- convert a list of tuple to a list or MPair. 
fromListToMPair :: [(a,a)] -> [MPair a] 
fromListToMPair [] = [] 
fromListToMPair ((a, b):xs) = (MPair a b) : fromListToMPair xs 

-- the inverse of the previous one 
fromMPairToList :: [MPair a] -> [(a,a)] 
fromMPairToList [] = [] 
fromMPairToList ((MPair a b):xs) = (a, b) : fromMPairToList xs 

-- A test case 
testList = [(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)] 

이동이 ghci하고 테스트하기 위해,

>>> fromMPairToList $ sort $ fromListToMPair testList 
[(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)] 
-- add a test to check the stability of your order. 
>>> fromMPairToList $ sort $ sort $ fromListToMPair testList 
[(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)] 
-- ok this is stable 

이되지 귀하의 요구 사항을 만족 않지만, 그것이 내가 설명하고 싶은 또 다른 방법입니다.
사실 튜플 목록을 정렬하기위한 고전적인 규칙을 구현했습니다.
이제 "주문"을 정의하려고합니다. 그런 다음 MPair에 대한 Ord 인스턴스를 재정의합니다.내가 ghci로 테스트,

>>> fromMPairToList $ sort $ fromListToMPair testList 
[(4,1),(4,2),(2,3),(2,0),(2,1),(1,3),(1,1),(0,3),(0,1)] 
>>> fromMPairToList $ sort $ sort $ fromListToMPair testList 
[(0,1),(0,3),(2,0),(1,1),(2,3),(1,3),(2,1),(4,1),(4,2)] 
-- no this won't work, this is not an ordering, you cannot sort. 

을 다시 실행하면 같은,

instance (Ord a, Num a) => Ord (MPair a) where 
    compare p@(MPair a b) q@(MPair c d) 
      | p == q  = EQ 
      | check a b c d = LT 
      | otherwise  = GT 
       where 
        pred x y = (abs (x - y)) < 2 
        check a b c d = pred a c && pred b d 

은 그 때 나는 당신이 필요로하지 정렬, 주문의 안정성을 만족하지 실현.

마지막으로, 당신이 기준으로 튜플 목록에 순서를 정의하지 않는다고해서 말이되지 않는다고 말하고 싶습니다. 당신의 기준은 판별 자이며, 당신은 두 개의 하위 데이터 그룹을 만들 수 있습니다. ([기준 x는 참이다], [기준 x는 참이 아니다]). 평소와 같이 튜플의 목록을 정렬하고 두 개의 별개의 그룹을 만드는 지정 함수 (기준에 따라)를 정의하십시오.

추신 : 귀하의 기준에 따라 기능을 사용하여 데이터를 주문할 수는 있지만 그 방법을 알 수는 없습니다.