相关疑难解决方法(0)

我最近了解到Data.Function.fix,现在我想在任何地方应用它.例如,每当我看到递归函数时,我想" fix"它.所以基本上我的问题是我应该在何时何地使用它.

为了使它更具体:

1)假设我有以下代码用于分解n:

f n = f' n primes
  where
    f' n (p:ps) = ...
    -- if p^2<=n: returns (p,k):f' (n `div` p^k) ps for k = maximum power of p in n
    -- if n<=1: returns []
    -- otherwise: returns [(n,1)]

如果我改写它fix,我会获得一些东西吗？失去什么？有可能,通过重写一个显式的递归到fix-version我会解决,反之亦然会创建一个堆栈溢出？

2)处理列表时,有几种解决方案:递归/修复,foldr/foldl/foldl',可能还有别的东西.关于何时使用每种方法,是否有任何一般指导/建议？例如,您是否会使用foldr无限的素数列表重写上面的代码？

可能还有其他重要问题没有在这里讨论.欢迎任何与使用相关的其他评论fix.

我正在通过"现在学习Prolog"在线书籍来获取乐趣.

我正在尝试编写一个谓词,该谓词遍历列表的每个成员并使用累加器向其中添加一个谓词.我已经很容易做到了,没有尾递归.

addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).

但我已经读过,出于性能原因,最好避免这种类型的递归.这是真的？总是使用尾递归被认为是"好习惯"吗？是否值得努力使用累加器来养成良好的习惯？

我试图将此示例更改为使用累加器,但它会反转列表.我怎么能避免这个？

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).

我是麻省理工学院开放式课程的SICP课程的初学者,使用视频讲座和在线提供的书籍.昨天我遇到了一个例子,它询问我们是否可以编写一个程序来计算改变任何给定金额的方法的数量.

这个问题有一个简单的解决方案作为递归过程:

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

如果你想检查更多,我从这里拿走它.

他们通过添加以下内容计算使用K种硬币改变数量(N)的数量(N):

1. 没有第一类硬币的改变A的方式(X)的数量.

2. 改变(A - D)的方式(Y)的数量,其中D是fisrt硬币的面额,使用所有K种类型的硬币.

问题是,我只是不明白这一点.接着,他们试图解释说:

"要明白为什么这是真的,请注意改变的方法可以分为两组:那些不使用任何第一种硬币的那些,以及那些使用任何第三种硬币的方法.因此,改变方法的总数对于某些金额等于不使用任何第一种硬币进行金额变更的方式的数量,加上假设我们使用第一种硬币进行变更的方式的数量.(最后一句话)与加法N = X + Y相同？)但后一个数字等于使用第一种硬币后剩余数量的变化方式的数量.(使用此硬币后,它们指的是方式是否使用第一种硬币进行更改？) " …

我突然处于一个递归语言类(sml)中,并且递归对我来说还不是很合理.我正在考虑方形瓷砖的地板有时是整数乘法的模型或隐喻的方式,或者Cuisenaire Rods是加法和减法的模型或模拟.有没有人可以分享任何这样的模型？

我只是无法绕过递归.我理解所有的概念(将解决方案分解为更小的案例),并且在我一遍又一遍地阅读之后我能理解解决方案.但我永远无法弄清楚如何使用递归来解决问题.有没有系统的方法来提出递归解决方案？

有人可以在尝试解决以下递归问题时向我解释他们的思考过程:"使用递归返回字符串的所有排列".

这是我解决这个问题的思考过程的一个例子.

• 检查字符串长度是否等于2.如果是,则交换值(基本情况)
• 否则:对于每个第一个值返回第一个值+递归(没有第一个值的字符串)

有人可以给我一些提示来改变我的思维过程或以更好的方式思考递归,这样我就可以解决递归问题,而无需查找答案.

编辑:这是我编写另一个解决这个问题的方法的思考过程.

• 基本情况是字符串长度= 0时
• 如果它不是基本情况,那么对于字符串的每个第一个字母,将第一个字母插入到字符串的每个排列的每个位置,而不是第一个字母
• 例如:字符串是"abc",第一个字母是a,所以在"bc"的排列的每个位置插入一个.[bc,cb] => [abc,bac,bca,acb,cab,cba]

伪代码

permutation(String s, List l) {
   if(s.length() == 0) {
      return list;
   }
   else {
     String a = s.firstLetter();
     l = permutation(s.substring(1, s.length) , l)

     for(int i = 0; i < s.length(); i++) {            
        // loop that iterates through list of permutations 
        // that have been "solved"
        for(int j=0; j < l.size(); j++) {                 
           // loop that iterates through all positions of every 
           // …

经过长时间的搜索谷歌我无法找到一个明确的答案:在Prolog自己做递归很容易.我的主要问题是了解放置累加器和计数器的位置.这是一个例子:

nXlist(N,X,[X|T]):-
    N \=0,
    N1 is N-1,
    nXList(N1,X,T).
nXList(0,_,[]).

media([X|L], N, Soma):-
   media(L, N1, Soma1),
   N is N1 + 1,
   Soma is Soma1 + X.
media([], 0, 0).

在第一个例子中,我在递归之前使用了一个计数器,但在第二个例子中,我在AFTER之后使用它.我之所以做到这一点的原因是所谓的尝试并看到原因我真的无法理解为什么有时候之前,有时是之后......

Fibonacci的这种实现很容易理解但很慢:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

实施Fibonacci之后很难理解,但速度非常快.它会立即在我的笔记本电脑上计算出第100,000个斐波纳契数.

fib = fastFib 1 1

fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)

关于后一种实施,这里发生了什么神奇的事情,它是如何运作的？

我正在编写一个删除json字符串中的空格的函数.我需要知道我正在处理的当前字符是否被包围",或者它是否在转义字符之后\.所以我需要两个param用于此功能.

这是当前的实现.但我不认为这是懒惰的.如何在json字符串上使用"filter"或"map"使其变得懒惰？

compressJson :: String -> String
compressJson json = compress json False False ""
    -- compress params: json, inStr, aferEscape, acc
    where compress []          _     _     acc = acc
          compress ('\"' : xs) inStr False acc = compress xs (not inStr) False (acc ++ "\"")
          compress ('\\' : xs) inStr False acc = compress xs inStr       True  acc
          compress (x    : xs) inStr True  acc = compress xs inStr       False (acc ++ ['\\', x])
          compress …