Idris 中的字符串替换函数

Question

在 Idris 中，字符串是基本类型，而不是像 Haskell 中那样的列表。因此，我希望有某种原始的 replace : (needle : String) -> (replacement : String) -> (haystack : String) -> String 函数如 la Data.Text.replace. I have not been able to find this. But I thought, perhaps I will be able to find some replace : Eq a => (needle : List a) -> (replacement : List a) -> (haystack : List a) -> List a function a la Data.List.Utils.replace, since Idris does provide unpack : String -> List Char and pack : Foldable t => t Char -> String. However, I have not been able to find replace for Lists defined in Idris, either. I have searched the documentation and the GitHub repo 用于一些事情，并在 REPL 中使用 :browse 进行探索，但都没有运气。当然，老 Idris 的 replace 函数适用于处理类型，而不是字符串...（这在某种程度上让我很高兴，但并没有解决我的问题）。

最后，我从 Haskell 移植了 Data.List.Utils.replace，但我想知道它的性能，更糟糕的是，它并不完整。此外，对于我通常认为的原始操作（假设字符串是原始操作），它需要大量代码。

spanList : (List a -> Bool) -> List a -> (List a, List a)
spanList _ [] = ([],[])
spanList func list@(x::xs) =
  if func list
  then
    let (ys,zs) = spanList func xs
    in (x::ys,zs)
  else ([],list)

breakList : (List a -> Bool) -> List a -> (List a, List a)
breakList func = spanList (not . func)

partial
split : Eq a => List a -> List a -> List (List a)
split _ [] = []
split delim str =
  let (firstline, remainder) = breakList (isPrefixOf delim) str in
  firstline :: case remainder of
                    [] => []
                    x => if x == delim
                         then [] :: []
                         else split delim (drop (length delim) x)

partial
strReplace : String -> String -> String -> String
strReplace needle replacement =
  pack . intercalate (unpack replacement) . split (unpack needle) . unpack

我将重塑它，直到我把它全部完成，因为我看不出为什么它不能全部完成，但与此同时，我错过了什么？人们真的在 Idris 中做的字符串操作太少以至于根本不可用吗？我假设 contrib 中至少会有一些东西。你如何在 Idris 中进行字符串替换？

Answer 1

对于后来发现此问题并想要实施的任何人，这是我目前所拥有的：

module ListExt

%default total
%access public export

splitOnL' : Eq a => (delim : List a)    -> {auto dprf : NonEmpty delim   }
                 -> (matching : List a) -> {auto mprf : NonEmpty matching}
                 -> List a -> (List a, List (List a))
splitOnL' _ _ [] = ([], [])
splitOnL' delim m@(_::m') list@(x::xs) =
  if isPrefixOf m list
  then
    case m' of
      [] => ([], uncurry (::) $ splitOnL' delim delim xs)
      (m_ :: ms) => splitOnL' delim (m_ :: ms) xs
  else
    let (l, ls) = splitOnL' delim delim xs in
    (x :: l, ls)

splitOnL : Eq a => (delim : List a) -> {auto dprf : NonEmpty delim}
                -> List a -> List (List a)
splitOnL delim [] = []
splitOnL delim list@(_::_) = uncurry (::) $ splitOnL' delim delim list

substitute : Eq a => List a -> List a -> List a -> List a
substitute [] replacement = id
substitute (n :: ns) replacement = intercalate replacement . splitOnL (n :: ns)

strReplace : String -> String -> String -> String
strReplace needle replacement = pack . substitute (unpack needle) (unpack replacement) . unpack

我可能会尝试提交 PR 以将其包含在 Idris 的基础库中。警告：我没有对此进行过性能测试，甚至根本没有对其进行过严格测试；我有运行大约十几个案例，它似乎是正确的。如果你只是分析算法，你会发现它并不像你希望的那样高效。到目前为止，我还没有成功地在保持整体性的同时实现更高效的版本。

Idris 中的字符串替换函数

String replace function in Idris

string

replace

idris