Добавление элемента в список

Question

Я хочу написать функцию, которая добавляет элемент в список в правильном порядке, скажем 1 в [2, 3]. Я новичок в haskell и вам нужна помощь в том, как это сделать, не используя Ord.

Answer 1

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

insert :: Ord a => a -> [a] -> [a] 

insert x [] = [x] 

insert x (y:ys) 
    | x > y  = y : insert x ys 
    | otherwise = x : y : ys 

Однако это вряд ли будет эффективным для вашего случая использования. Проблема со списком заключается в том, что вы в конечном итоге создаете новую копию большой части позвоночника многократно с такой проблемой вставки. Вы также должны сканировать линейно по всему списку, пока не найдете нужное место, которое не является самым быстрым способом поиска правильного местоположения.

Возможно, вам будет лучше использовать структуру данных, такую ​​как таковая в Data.Set или Data.IntSet. Обычно это O (log n) для вставки, потому что они используют деревья или другие структуры данных, которые позволяют больше общего доступа, чем список, и быстро найти нужное место.

Answer 2

Ваш вопрос не имеет смысла, не используя Ord.

Использование Ord, функция, которую вы хотите, insert

Функция вставки принимает элемент и список и вставляет элемент в список на последней позиции, где еще меньше или равен следующим элемент.