使用foldr定义我自己的isPrefixOf而不使用递归

Question

我正在做一项编程作业，我必须仅使用、和 cons 定义我自己的isPrefixOffrom版本（因此没有递归）。我得到的提示是 的返回值本身应该是一个函数。有人可以帮助我理解如何应用这个事实吗？我对结构的猜测如下。Data.Listfoldrmapfoldr

startsWith :: String -> String -> Bool
startsWith s1 s2 = (foldr (???) ??? s1) s2

我可以定义自己的辅助函数。出于好奇，这是来自宾夕法尼亚大学 CIS 552 的作业。

Answer 1

编辑：事实证明，通过折叠模式而不是字符串，代码变得更简单、更短，就像

"" `isPrefixOf` undefined

作品。谢谢@dfeuer 和@WillNess。这是更新后的程序：

isPrefixOf pattern s = foldr g (const True) pattern s
    where
        g x r (h:t)
          | x == h    = r t
          | otherwise = False

它的工作方式几乎与下面的程序相同，因此请参阅该程序的说明。

我设法解决了这个问题，只使用foldr：

isPrefixOf :: String -> String -> Bool
p `isPrefixOf` s = isPrefixOfS p
    where
        isPrefixOfS 
            = foldr 
                (\c acc -> 
                    \str -> case str of
                        x:xs -> if c == x
                                then acc xs
                                else False
                        []   -> True 
                    )
                null
                s

这是解释。

为了创建函数isPrefixOf，我们需要这样：

isPrefixOf pattern s 
  = case pattern of
      [] -> True
      x:xs -> if (null s) then False
              else if (head s) /= x
                   then False
                   else xs `isPrefixOf` (tail s)
              

好吧，让我们简化一下 - 让我们创建一个名为 的函数，isPrefixOfS它只接受一个模式，并s自动与该模式进行比较。我们需要构建这个嵌套函数链：

-- Pseudocode, not actual Haskell

\p -> case p of 
        [] -> True
        x:xs -> if x /= (s !! 0)
                  then False
                  else <apply xs to> \q -> case q of [] -> True
                                                     x:xs -> if x /= (s !! 1) -- Note that we've incremented the index
                                                             then False
                                                             else <apply xs to> \r -> ....

这似乎是不言自明的 - 如果需要进一步解释，请在评论中告诉我。
好吧，我们可以看到该链具有递归属性，其中 的最后一个字符s将在嵌套最深的 lambda 中进行比较。所以我们需要从右到左嵌套 lambda。我们可以用什么来做到这一点？foldr。

isPrefixOfS 
            = foldr -- Folding from right to left across `s`
                (\c acc -> -- `c` is the current character of `s`, acc is the chain of nested functions so far
                    \str -> -- We return a function in the fold that takes a String
                      case str of
                        -- If the string is not null:
                        x:xs -> if c == x   -- If the head of the string is equal to the current character of s,
                                then acc xs -- Then pass the tail of the string to the nested function which will compare it with subsequent characters of s
                                else False -- Otherwise we return false
                
                        -- If the string is null, we have completely matched the prefix and so return True
                        []   -> True  
                    )
                null -- Innermost nested function - we need to make sure that if the prefix reaches here, it is null, i.e. we have entirely matched it
                s

现在我们使用这个isPrefixOfS函数p：

p `isPrefixOf` s = isPrefixOfS p

编辑：我刚刚发现这篇文章使用类似的逻辑来实现zip，foldr您可能也想看看。