Самый элегантный подход к написанию списка функция перенумерации


Я пишу функцию со следующей сигнатурой:

(Ord a) => [a] -> [Int]

Это семантика найти приказ-сохранить отображение списка объектов в список Инт- ов.

Версия моя:

import Data.List
import Data.Map (Map, (!))
import qualified Data.Map as Map 

renumber :: (Ord a) => [a] -> [Int]
renumber list = let mapping = buildmapping list Map.empty in
                map (mapping!) list
        where
            -- buildmapping :: (Ord a) => [a] -> Map a Int -> Map a Int
            buildmapping list mapping = let
                mapped = Map.keys mapping
                (rest, nextindex) = if (null mapped) then
                      (list, 1) else
                      (filter (> maximum mapped) list,
                        (1+) $ maximum $ Map.elems mapping)
                in case rest of
                  [] -> mapping -- nothing left, return
                  _  -> buildmapping rest $ Map.insert (minimum rest) nextindex mapping


278
4
задан 21 апреля 2011 в 07:04 Источник Поделиться
Комментарии
1 ответ

Я думаю, что сортировка подхода будет проще, чем с использованием карты. Основная идея заключается в том, что мы сортируем список, присвоить каждому элементу значение, основанное на его позиции в списке, а затем отменить сортировку и принимают значение, присвоенное каждому пункту. Для того, чтобы отменить сортировку мы должны запомнить расположение каждого элемента было до сортировки. Итак, мы получаем следующее (показано на примере ввода ["в", "С", "В", "С"]):


  1. Комментировать каждый пункт с его индексом. Так В ["В","С","В","С"] становится [(1, "а"), (2, "с"), (3, "Б"), (4, "с")].

  2. Сортировать аннотациями товаров по их стоимости. Так, например, мы получаем [(1, "а"), (3, "Б"), (2, "с"), (4, "с")]

  3. Группа отсортированный аннотациями товаров по их ценности, так что повторяющиеся элементы зададут тот же номер на следующем шаге. В Примере: [[(1, "а")], [(3, "Б")], [(2, "с"), (4, "с")]]

  4. Теперь снова комментировать каждую группу с ее индексом. В Примере: [(1, [(1, "а")]), (2, [(3, "Б")]), (3, [(2, "с"), (4, "с")])].

  5. Разогнуть группы, так что вместо того, чтобы список групп, у нас есть список снова элементы, где каждый элемент имеет старый индекс и новый индекс. В пример: [(1, (1, "а")), (2, (3, "Б")), (3, (2, "с")), (3, (4, "с"))].

  6. Теперь отменить сортировка по сортировка предметов по их старый индекс. В пример: [(1, (1, "а")), (3, (2, "с")), (2, (3, "Б")), (3, (4, "с"))].

  7. Наконец карту каждый элемент своего нового индекса. Так, например, мы получаем на выходе [1,3,2,3].

Это приводит к следующим кодом:

{-# LANGUAGE TupleSections #-}
import Data.List
import Data.Function (on)
import Data.Ord (comparing)

renumber :: (Ord a) => [a] -> [Int]
renumber = map fst . unsort . number . indexAndSort
where
indexAndSort = sortBy (comparing snd) . zip [1..]
number = concatMap (\(i,xs) -> map (i,) xs) . zip [1..] . groupBy ((==) `on` snd)
unsort = sortBy (comparing (fst . snd))

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

4
ответ дан 21 апреля 2011 в 02:04 Источник Поделиться