Метод класса с гетерогенным рекурсивным бесконечным и зависимым аргументом типа

Я застрял, играя с "гетерогенным рекурсивным бесконечным типом" (какое-нибудь название получше?).

Пусть следующая рабочая "Глубокая сортировка"

class Ord f => DeepSort f where
  deepSort :: f -> f
  deepSort = id

instance DeepSort Int where
-- and so on ...

instance DeepSort a => DeepSort [a] where
  deepSort = sort . map deepSort
instance DeepSort a => DeepSort (Maybe a) where
  deepSort = fmap deepSort
-- and so on ...

Например

sample :: [Maybe [[Int]]]
sample = [ Just [[5, 3, 7, 1], [6, 0]]
         , Nothing
         , Just [[8, -1], []]
         ]

main = print $ deepSort sample

пишет

[Nothing,Just [[],[-1,8]],Just [[0,6],[1,3,5,7]]]

но теперь я хочу параметризовать критерии сортировки, например (не работает)

main = print $ deepSortBy sample
                          ( By   (compare `on` someCriteria1)
                          $ By   (compare `on` someCriteria2)
                          $ By   (compare `on` someCriteria3)
                          $ Then (compare `on` someCriteria4)
                          )

Моя проблема заключается в том, как определить аргумент "гетерогенный рекурсивный бесконечный тип" (или как его там еще назвать).

Я думаю, что это

By (f1 (f2 ... (fN a) ...)
   (By (f2 ... (fN a) ...)
       ...
               Then (fN a)
   )

Примечание: в примере deepSort вложенные контейнеры были отсортированы по возрастанию с экземпляром Ord по умолчанию; смысл deepSortBy заключается в предоставлении явных Ord функций сравнения для каждого вложенного контейнера. Поскольку контейнеры f1 (f2 (f3 ... (fN a)...), критерии могут/должны быть указаны как By comparer1 (By comparer2 (By .... Но может быть лучше другой подход, конечно.

кроме того, вероятно, существует лучший "подход Haskell" НО я бы хотел (если возможно)

  • Существует какое-то прямое решение моего подхода "по классам"?

  • Какой лучший "подход Haskell" к такой проблеме?

  • Какая-то библиотека решает это?

Спасибо!!!

ОТРЕДАКТИРОВАНО

У меня есть возможный подход к решению (опубликуйте как решение, оно работает! :D)


recursion haskell dependent-type
person josejuan    schedule 08.10.2014    source источник
comment
Не могли бы вы немного пояснить свой пример? Смотрите, ваш sample — это список Maybe; поэтому, когда вы (глубоко) сортируете, вам нужно сравнить эти Maybe, но вы начинаете со сравнения по length.   -  person MigMit    schedule 08.10.2014
comment
@MigMit, вы можете видеть, что deepSort относится к Data.List.sort, как deepSortBy к Data.List.sortBy (но вместо этого используются только списки, обобщающие с использованием class). Кроме того, deepSortBy можно записать как map deepSortBy . sortBy f (с другим результатом), но это не главное. Я добавил примечание, разъясняющее это (я желаю).   -  person josejuan    schedule 08.10.2014
comment
Как определяются By и Then? Если у вас возникли проблемы с определением их типов, вы должны хотя бы уметь определять типы someCriteria1, someCriteria2, someCriteria3 и someCriteria4.   -  person Cirdec    schedule 08.10.2014
comment
@Cirdec действительно не знаю, я отредактировал свой вопрос, добавив возможный подход (используя newtype для бесконечного типа), но он не работает... :'(   -  person josejuan    schedule 08.10.2014

Ответы (1)


arrow_upward
4
arrow_downward

Любая структура, которую можно пройти, может быть отсортирована. . Оба Maybe и [] являются Traversable. Мы можем уловить идею о том, что все Traversable Functor можно отсортировать по какому-то признаку, используя следующее определение sortBy. Он работает, перечисляя все данные в структуре, сортируя этот список, затем обходя структуру слева направо, заменяя каждый элемент первым элементом в списке и перенося оставшуюся часть списка.

import qualified Data.List as List

import Data.Foldable
import Data.Traversable

sortBy :: Traversable f => (a -> a -> Ordering) -> f a -> f a
sortBy o f = snd . mapAccumL (\(h:t) _ -> (t, h)) sorted $ f
    where
        sorted = List.sortBy o . toList $ f

Когда вы что-то deepSortBy, вы просто применяете функцию внутри Traversable Functor перед сортировкой. Это просто удобная функция, которая фиксирует этот шаблон.

deepSortBy :: Traversable f => (b -> b -> Ordering) -> (a -> b) -> f a -> f b
deepSortBy o f = sortBy o . fmap f

Мы можем удобно записать сортировку вашей выборки по deepSortBy.

sample :: [Maybe [[Int]]]
sample = [ Just [[5, 3, 7, 1], [6, 0]]
         , Nothing
         , Just [[8, -1], []]
         ]

sampleSorter :: [Maybe [[Int]]] -> [Maybe [[Int]]]
sampleSorter = 
    deepSortBy (compare `on` isJust) $
    deepSortBy (compare `on` length) $
    deepSortBy (compare `on` listToMaybe) $
    sortBy compare

Последняя строка, sortBy compare, эквивалентна deepSortBy compare id. listToMaybe позволяет избежать ошибки, которую выдает head.

Повторно используйте более глубокие сравнения, чтобы разорвать связи

Обратите внимание, что это не использует более глубокое сравнение, чтобы разорвать связи во внешних сравнениях. Например, sample сортируется как

[Nothing,Just [[0,6],[1,3,5,7]],Just [[],[-1,8]]]

Just [[0,6],[1,3,5,7]] и Just [[],[-1,8]] равны при сравнении isJust, а [[0,6],[1,3,5,7]] и [[],[-1,8]] равны при сравнении length. Если бы для разрыва этих связей использовались внутренние сравнения, listToMaybe поставил бы их в противоположном порядке. Если желаемый результат

[Nothing,Just [[],[-1,8]],Just [[0,6],[1,3,5,7]]]

нам пришлось бы проделать немного больше работы, чтобы зафиксировать внутренние сравнения.

person Cirdec    schedule 08.10.2014
comment
Идеально @Cirdec! Я искал class (хотя и уродливое) решение, но ваше решение именно то, что я искал. Спасибо! С другой стороны, решение на основе class может избежать преобразования from/to List. Может ли ваша версия обойти это? - person josejuan; 09.10.2014
comment
@josejuan Если вы добавите class Sortable f where sortBy :: (a -> a -> Ordering) -> f a -> f a, вы можете сделать его экземпляры специализированными для [] (sortBy = List.sortBy) или Maybe (sortBy = const id). Затем вы замените ограничение Traversable f на Functor f, Sortable f или просто Sortable f, если вы решите, что все Sortable должно также быть Traversable, Foldable или Functor. - person Cirdec; 09.10.2014
comment
Я отмечаю, что все это также должно работать с lens Traversals... безумно кудахчет... - person Ørjan Johansen; 09.10.2014
comment
Если посмотреть на это более серьезно, комбинатор partsOf, кажется, делает это очень просто: deepSortByOf t o f = partsOf t %~ sortBy o . map f - person Ørjan Johansen; 10.10.2014