CODEWITHSUNDEEP
haskell
Carrot
Carrot

Reputation: 39

How can i make Insert_sort high-order-function in Haskell

plz watch my code

insert x [] = [x]
insert x (y:ys)
    | x < y = x:y:ys
    | x == y = y:ys ++ [x]
    | otherwise = y:insert x ys

insert_sort [] = []
insert_sort (x:xs) = insert x (insert_sort xs)

insert_pair (x,y) [] = [(x,y)]
insert_pair (x,y) ((a,b):yd)
                     | x > a = (a,b):insert_pair (x,y) yd
                     | otherwise = (x,y):(a,b):yd

insert_sort_pair [] = []
insert_sort_pair (x:xs) = insert_pair x (insert_sort_pair xs)

insert_high f [] = []
insert_high f (x:y:ys)
            | f x y = x:y:ys
            | otherwise = y:insert x ys
insert_high f ((a,b):(c,d):yd)
            | f a c = (a,b):insert_pair (c,d) yd
            | otherwise = (a,b):(c,d):yd

insert_sort_high f [] = []
insert_sort_high f (x:xs) = insert_high (f) x (insert_sort_high (f) xs)

I want to make insert_sort-high can do both insert_sort and insert_pair_sort. "insert_sort_pair" compare the number in (number,symbol). For example:

insert_sort_high (<) [3,5,2,1,4] -> [1,2,3,4,5]
insert_sort_high (>) [(2,'a'),(3,'b'),(1,'c')] -> [(1,'c'),(2,'a'),(3,'b')]

But, it doesn't work... how can i fix it?

Upvotes: 0

Views: 62

Answers (1)

rampion
rampion

Reputation: 89043

First, a fundamental misunderstanding.

Write a type for insert_high - it should probably be (a -> a -> Bool) -> [a] -> [a]. But you've written a specialization for lists of tuples, so you've forced it to be less general than that.

You can only cover the general case. You're being misled by your examples.

I'd argue what you really want is

λ insert_sort_high (<) [3,5,2,1,4]
[1,2,3,4,5]
λ insert_sort_high (\(x,y) (a,b) -> x < a) [(2,'a'), (3,'b'), (1,'c')]
[(1,'c'),(2,'a'),(3,'b')]

The latter can be written a little more easily as

λ :m +Data.Function
λ insert_sort_high ((<) `on` fst) [(2,'a'), (3,'b'), (1,'c')]
[(1,'c'),(2,'a'),(3,'b')]

Of course, that's only if you only want sorting to be on the first element of the pair.

λ insert_sort_high ((<) `on` fst) [(2,'a'), (3,'b'), (1, 'a'), (1,'b'), (1,'c'), (1,'a')]
[(1,'a'),(1,'c'),(1,'b'),(1,'a'),(2,'a'),(3,'b')]

If you want to sort by the entire pair, you can do that too

λ (1,'a') < (1,'b')
True
λ (1,'z') < (2,'a')
True
λ insert_sort_high (<) [(2,'a'), (3,'b'), (1,'a'),(1,'b'),(1,'c'), (1,'a')]
[(1,'a'),(1,'a'),(1,'b'),(1,'c'),(2,'a'),(3,'b')]

But I digress.

With that in mind all you really need to do is delete your tuple case, and clean up some typos.

insert_high :: (a -> a -> Bool) -> a -> [a] -> [a]                   
insert_high _ x [] = [x]                                             
insert_high f x (y:ys)                                               
            | f x y = x:y:ys                                         
            | otherwise = y : insert_high f x ys                     

insert_sort_high _ [] = []                                           
insert_sort_high f (x:xs) = insert_high f x (insert_sort_high f xs)

Upvotes: 3

Related Questions