相关疑难解决方法(0)

我很抱歉这样的问题.我不是太肯定的区别:,并++在Haskell运营商.

x:y:[] = [x,y]  

也

[x] ++ [y] = [x,y]

至于为我提出这个问题的反向功能,

reverse ::[a]->[a]
reverse [] = []
reverse (x:xs) = reverse(xs)++[x]

以下为什么不工作？

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

给出类型错误.

我目前正在通过在线学习你的Haskell书籍的方式,并且已经到了一个章节,作者正在解释一些列表连接可能效率低下:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下.作者提出的解决方案是使用定义为的"差异列表"

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么DiffList在某些情况下比简单串联更具计算效率.有人可以用简单的语言向我解释为什么上面的例子是如此低效,以及DiffList以什么方式解决了这个问题？

我只使用了3种函数式语言 - scala,erlang和haskell,但在所有这三种语言中,构建列表的正确方法是将新数据添加到前面然后反转它而不是仅仅追加到最后.当然,您可以附加到列表,但这会导致构建一个全新的列表.

为什么是这样？我可以想象这是因为列表在内部实现为链接列表,但为什么它们不能仅作为双链表实现,所以你可以追加到最后没有惩罚？是否有某些原因所有功能语言都有此限制？

我知道quicksort的O(n log n)平均时间复杂度.伪快速排序(当你从足够远的地方看它,具有适当高的抽象级别时只是一个快速排序),通常用于演示函数语言的简洁性如下(在Haskell中给出):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

好的,所以我知道这件事有问题.最大的问题是它没有排序,这通常是quicksort的一大优势.即使这没关系,它仍然需要比典型的快速排序更长的时间,因为它在分区时必须进行两次列表传递,然后它会进行昂贵的附加操作以将其拼接回来.此外,选择第一个元素作为枢轴不是最佳选择.

但即便考虑所有这些,这个快速排序的平均时间复杂度与标准快速排序不同吗？即,O(n log n)？因为追加和分区仍然具有线性时间复杂度,即使它们效率低下.

该DLIST包包含DList数据类型,它有大量的实例,但不是Foldable或Traversable.在我看来,这是两个最"类似列表"的类型.是否存在DList不是这些类的实例的性能原因？

而且,封装确实实现foldr和unfoldr,但是没有其他的折叠功能.

在CodeReview的答案中,提问者和回答者似乎都对(++)运算符表示不屑.这是由于它的速度(导致算法明确地在O(n ^ 2)中运行,其中n是列表的长度iirc)？如果不进行其他测试,这是否是预优化,因为Haskell因难以推断时间复杂性而闻名？其他人是否应该避免程序中的(++)运算符？

我正在尝试解决Haskell中的函数式编程练习的问题.我必须实现一个函数,在给定一个具有偶数个字符的字符串的情况下,该函数返回相同字符串并交换字符对.

像这样:

"helloworld" - >"ehllworodl"

这是我目前的实施:

swap :: String -> String
swap s = swapRec s ""
  where
    swapRec :: String -> String -> String
    swapRec [] result       = result
    swapRec (x:y:xs) result = swapRec xs (result++[y]++[x])

我的函数返回正确的结果,但编程练习是定时的,看起来我的代码运行得太慢了.

我能做些什么来让我的代码运行得更快,或者我是否采用了错误的方法解决问题？

当我阅读第 13 章时，Real World Haskell我想到了Difference Lists.
作者说，在命令式语言中，如果我们想将一个元素附加到列表中，成本将是O(1)因为我们将保留一个指向最后一个元素的指针。但是在 Haskell 中，我们有immutable对象，所以我们每次都需要遍历列表并将元素追加到末尾，因此0(n).

而不是[1,2,3]++[4]++[5]
我们可以使用部分应用程序：(++4).(++5) [1,2,3]。

我不明白这是怎么更有效，因为：
-当我这样做(++[5]) [1,2,3]它仍然是O(n)接着又0(n)为(++4)

引用

There are two very interesting things about this approach. The first is that the cost of a partial application is constant, so the cost of many partial applications is linear. The second is that when we finally provide a [] value to
unlock the …

我是Haskell的新手.我试图了解haskell如何处理递归函数调用以及它们的惰性求值.我所做的实验只是在C++和Haskell中构建二进制搜索树,并分别在后序中遍历它们.C++实现是具有辅助堆栈的标准实现.(我只是在访问它时打印出元素).

这是我的haskell代码:

module Main (main) where

import System.Environment (getArgs)
import System.IO
import System.Exit
import Control.Monad(when)
import qualified Data.ByteString as S

main = do
     args <- getArgs
     when (length args < 1) $ do
          putStrLn "Missing input files"
          exitFailure

     content <- readFile (args !! 0)
     --preorderV print $ buildTree content
     mapM_ print $ traverse POST $ buildTree content
     putStrLn "end"


data BSTree a = EmptyTree | Node a (BSTree a) (BSTree a) deriving (Show)
data Mode = IN | POST | …

我正在阅读Haskell课程的介绍,他们正在引入着名的河内塔问题作为头等课程的作业.我被诱惑并写了一个解决方案:

type Peg = String

type Move = (Peg, Peg)

hanoi :: Int -> Peg -> Peg -> Peg -> [Move]
hanoi n b a e
  | n == 1 = [(b, e)]
  | n > 1 = hanoi (n - 1) b e a ++ hanoi 1 b a e ++ hanoi (n - 1) a b e
  | otherwise = []

我已经玩了一点,看到它显然使用Tail Call Optimization,因为它在恒定的内存中工作.

Clojure是我大部分时间都在工作的语言,因此我遇到了编写Clojure解决方案的挑战.天真的被丢弃,因为我想写它来使用TCO:

(defn hanoi-non-optimized
  [n b a e]
  (cond
    (= n 1) [[b …

在使用 haskell 并为项目 euler n\xc2\xb040 寻找解决方案的过程中，我发现这段代码非常快：

 p = concat [show n | n <- [1..]]\ndl x = p !! x\n\ny = [10^a - 1| a<-[0..6]]\ns = [digitToInt (dl b)::Int | b <-y]\n

但这非常慢，慢了几百万倍

p = foldl1 (++) (map show [1..1000000])\ndl x = p !! x\n\ny = [10^a - 1| a<-[0..6]]\ns = [digitToInt (dl b)::Int | b <-y]\n

有人可以向我解释为什么吗？谢谢

今天我开始学习Haskell.我是函数式语言的新手,我很喜欢Haskell.

然而,我有一个关于它的设计的问题,这让我烦恼:从我到目前为止所理解的看起来像访问列表后面的元素看起来要复杂得多,因为访问元素到前面(类似于xs:x哪里xs::[a]和x::a似乎不可能).

(根据我的理解)可以将列表附加到另一个(xs++[a]),但它在运行时会花费更多(它需要遍历整个列表)并且它不能用于模式匹配.

为什么Haskell缺少这样的操作？

belongs :: Eq(a) => a -> [a] -> Maybe a

belongs e (h:t) = if ( h == e) then Nothing else belongs e t
belongs e [] = Just e


nub :: Eq(a) => [a] -> [a]
nub l = nub' l [] 
    where 
        nub' [] new_list = new_list
        nub' (h:t) new_list = nub' t (new_list ++ [(belongs h new_list)])

错误:

Occurs check: cannot construct the infinite type: a0 = Maybe a0
Expected type: [a0]
  Actual type: [Maybe a0] …