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이 완료되면, 하늘의 목록 또는 하나 개의 요소를 포함하는 목록 중 하나를 반환하는 것입니다 :

내 기능은 한 번리스트를 전달하고 목록의 머리를 정렬하려면 이 기능적인 방법을 어떻게 설계할까요?

저는 foldl에 대해 생각하고 있었고 일부는 haskell 마법과 함께 가고 싶었지만 현재는 붙어 있습니다. 사전에

감사

Answer 1

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

(안된)

아니면 배의 측면에서

:

(도 안된)

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

, 당신의 sortEm 함수 이름의

Answer 2

우선 오해의 소지가 있지만 인수 목록을 정렬하지 않지만 그 꼬리에 머리 요소 nserts. 공교롭게도, 두 번째로 첫 번째 인자를 삽입 이미 Data.List module의 insert 기능이있다, 그래서 동등성는 삽입하는 경우 항목을 삽입하는 경우에만 다시 당신에게 정렬 된 목록을 얻을 것이다,

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을 왼쪽에서 오른쪽으로 반대 방향으로 적용하면 나타납니다.

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 버전보다 더 lazier합니다 (덜 엄격합니다). 당신은 단지 코드 샘플을 찾는 경우

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