목록에 요소 추가

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을 사용하지 않으면 질문에 의미가 없습니다. 오드를 사용

원하는 기능 insert

이 삽입 기능은 다음에 여전히보다 작거나 같은 마지막 위치에있는 목록에 요소 요소 및 목록을 소요하고 삽입입니다 요소.