haskell список и функциональные

Question

Это домашнее задание, которое затихало последние пару дней.

У меня есть список, который я применяю для функции - нажатие каждого элемента вправо, если элемент рядом с ним меньше предыдущего.

Моя функция пройти по списку раз и сортировать голову списка:

sortEm lis@(x:y:xs) = if x > y then y: sortEm (x:xs) else lis 
sortEm [x] = [x] 
sortEm [] = [] 

myList (x:y:xs) = if x > y then sortEm lis else x:myList(y:xs) 
myList [] = [] 
myList [x] = [x] 

Но моя проблема в том, что когда-то, что sortem закончил он возвращается либо пустой список или список, содержащий один элемент, как бы я мог создать этот функциональный способ?

Я думал о складке, и некоторая магия haskell, чтобы согласиться с этим, но в настоящее время я застрял.

Заранее спасибо

Answer 1

myList []  = [] 
myList (x : xs) = sortEm (x : myList xs) 

(непроверенные)

Или в терминах складку:

myList = foldr cons [] 
    where cons x xs = sortEm (x : xs) 

(также непроверенные)

Answer 2

Прежде, ваше имя sortEm функции вводит в заблуждение, он не сортирует свой список аргументов, но i nserts его головной элемент в хвост. Как это происходит, есть insert функция уже в Data.List module, которая вставляет свой первый аргумент в 2, таким образом есть равноценности

sortEm (x:xs) === Data.List.insert x xs 

Теперь, вставка элемента будет только вам отсортированный список обратно, если вы вставка это в список, который уже отсортирован. Поскольку пустой список отсортирован, вот что делает функция myList, которую вы получили в ответе dave4420. Это "insertion" sort, постепенно вставляя элементы списка во вспомогательный список, изначально пустой. И это то, что вторая функция делает, что вы получили в dave4420 ответ:

insertionSort xs = foldr Data.List.insert [] xs 

Это «применяется sortem», т.е. вставки, «каждый элемент» только один раз. Для получения списка [a,b,c,...,z] это эквивалентно

insert a (insert b (insert c (... (insert z []) ...))) 

То, что вы, вероятно, означало в ваш комментарий, то для сравнения (и, возможно, подкачка) два соседних элемента «только один раз», известен как bubble sort. Конечно, делает только один проход по списку не будет выкручиваться, в общем случае:

bubbleOnce xs = foldr g [] xs where 
    g x [] = [x] 
    g x xs@(y:ys) | x>y  = y:x:ys -- swap x and y in the output 
       | otherwise = x:xs -- keep x before y in the output 

Теперь bubbleOnce [4,2,6,1,8] ==> [1,4,2,6,8]. Значение, которое вы ожидали, [2,4,1,6,8], было бы результатом применения функции складывания g в противоположном направлении, слева направо. Но это гораздо менее естественно, чтобы сделать здесь с Haskell списки:

bubbleOnce' [] = [] 
bubbleOnce' (x:xs) = let (z,h)=foldl g (x,id) xs in (h [z]) where 
    g (x,f) y | x>y  = (x, f.(y:)) -- swap x and y in the output 
      | otherwise = (y, f.(x:)) -- keep x before y in the output 

(редактировать :) см jimmyt's answer в эквиваленте, но простой и хороший вариант с использованием простой рекурсии.Он также более ленивый (менее строгий), чем версии fodlr и foldl.

Answer 3

-- if..then..else version 
sortEM  :: Ord a => [a] -> [a] 

sortEM (x:y:xs)  = if x < y 
         then x : sortEM (y:xs) 
         else y : sortEM (x:xs) 
sortEM b   = b 


-- guard version 
sortEM_G :: Ord a => [a] -> [a] 

sortEM_G (x:y:xs) 
    | x < y  = x : sortEM_G (y:xs) 
    | otherwise = y : sortEM_G (x:xs) 
sortEM_G b   = b