如何编写将元素插入排序列表的 Haskell 函数

Question

我尝试过这样的事情，但它不起作用我想要它做什么。我是 Haskell 的新手，我真的不知道该怎么做，还有什么问题。

 insert a (x:xs) = insert2 a (x:xs) []
            where insert2 el (x:xs) hd =
                    if (x:xs) == [] 
                        then []
                    else if ( a>=x && a < head(xs)) 
                        then hd ++ [x] ++ [a] ++ xs
                    else insert2 a xs hd++[x]
     
    main = do
        let list =[1 ,2 ,3 ,4 ,5 ,6]
        let out = insert 2 list
        print out

我得到的输出是 [2,2,3,4,5,6,1]

Answer 1

先来几款化妆品：

• 确保缩进是正确的。当复制/粘贴到 StackOverflow 中时，通常最好使用 ctrl+k 以代码块样式获取它。

• 匹配(x:xs)只是为了将整个事物传递到您的本地函数中是没有意义的。

• 省略不必要的括号并使用标准化的间距。

有了这个，你的代码就变成了

insert a allxs = insert2 a allxs []
 where insert2 el (x:xs) hd =
                if x:xs == [] 
                    then []
                else if a >= x && a < head xs
                    then hd ++ [x] ++ [a] ++ xs
                else insert2 a xs hd ++ [x]
 
main = do
    let list = [1, 2, 3, 4, 5, 6]
    let out = insert 2 list
    print out

从算法上讲，在这里使用“累加器参数”是没有意义的。直接对输入进行递归更容易，实际上更有效，并在插入完成后简单地传递剩余的尾部。还要记住有一个基本案例：

insert a [] = [a]
insert a (x:xs) = ...

您也不需要使用head. 您已经将 head 元素与x:xs模式进行了模式匹配。如果你确实需要另一个列表元素，你也应该在那里匹配它，比如

insert a (x:x':xs) = ...

...但实际上您不需要它，x足以确定要做什么。即，

insert a (x:xs)
 | a<=x       = -- if the list was ordered, this implies that now _all_
                -- its elements must be greater or equal a. Do you
                -- need any recursion anymore?
 | otherwise  = -- ok, `x` was smaller, so you need to insert after it.
                -- Recursion is needed here.

Answer 2

这里有一些提示。它比你制作的要简单得多。你绝对不需要辅助函数。

insert a [] = ??
insert a (x : xs)
  | a <= x = ???
  | otherwise = ???