Haskell中的字符串组合 [英] String combination in Haskell

问题描述

我正在用Haskell编写一种算法，该算法可简化无上下文语法，而且我一直在努力消除空值，特别是使用替代"语法.其他产品中可为空的非终端的数量.

I'm writing an algorithm in Haskell that simplifies context-free grammars and I've been struggling with the removal of null productions, more specifically with the "substitution" of nullable non-terminals in the other productions.

给出一个字符串，比方说"ASA"，我想返回一个通过删除字符"A"而构建的字符串列表.一，二，...每次出现.为了清楚起见，给定"ASA".我想返回此代码: ["SA"，"AS"，"S"] .

Given a string, let's say "ASA", I would like to return a list of strings built by removing the character "A" one, two, ... every time it appears. To be clear, given "ASA" I'd like to return this: ["SA", "AS", "S"].

在Python中，我做起来很容易，但是在Haskell中，我不知道如何遍历字符串并按我希望的方式操作它.可能是因为我仍然不习惯使用函数式编程.

In Python I did it quite easily, but in Haskell I don't know how to iterate over the string and manipulate it how I'd like to. Probably because I'm still not used tu functional programming.

推荐答案

基于库的方法:

给定的输入字符可能会或可能不会出现在任何输出部分字符串中.因此，让Haskell参与进来似乎很自然 Maybe型变压器.它类似于C ++中的 std :: optional .

我们可以有一个 expand 函数，该函数将与每个输入字符相关联的对应可能性的列表相关联:

We can have an expand function that associates to each input character a list of the corresponding possibilities:

$ ghci
 λ> 
 λ> st = "ASA"
 λ> 
 λ> expand ch = if (ch == 'A') then [ Just ch, Nothing ] else [ Just ch ]
 λ> 
 λ> map expand st
 [[Just 'A',Nothing],[Just 'S'],[Just 'A',Nothing]]
 λ> 

基本上，我们需要的是上述列出的可能性的笛卡尔积.可以使用高度多态的

What we need is basically the Cartesian product of the above lists of possibilites. A list Cartesian product can be obtained by using the highly polymorphic sequence library function:

 λ> 
 λ> sequence (map expand st)
[[Just 'A',Just 'S',Just 'A'],[Just 'A',Just 'S',Nothing],[Nothing,Just 'S',Just 'A'],[Nothing,Just 'S',Nothing]]
 λ> 

接下来，我们需要将例如 [Just'A'，Just'S'，Nothing] 更改为['A'，'S']，这在Haskell中是完全相同的作为"AS".所需的功能将具有其类型签名:

Next, we need to change for example [Just 'A', Just 'S', Nothing] into ['A', 'S'], which in Haskell is exactly the same thing as "AS". The required function would have as its type signature:

func :: [Maybe α] -> [α]

如果我们将此候选类型签名提交到 Hoogle ，我们很容易获得库函数

If we submit this candidate type signature into Hoogle, we readily get library function catMaybes:

 λ> 
 λ> import qualified Data.Maybe as Mb
 λ> 
 λ> Mb.catMaybes [Just 'A',Just 'S',Nothing]
 "AS"
 λ> 
 λ> map Mb.catMaybes (sequence (map expand st))
 ["ASA","AS","SA","S"]
 λ> 

，我们只需要删除完整的字符串"ASA"从最后一个列表中.

and we just have to remove the full string "ASA" from that last list.

当然，没有必要将其限制为 Char 数据类型.具有适当的相等性测试的任何类型都可以.特权字符"A"应设为可变参数.总体而言，这为我们提供了以下代码:

Of course, there is no need to restrict this to the Char data type. Any type with a proper equality test can do. And the privileged character 'A' should be made into a variable argument. Overall, this gives us the following code:

import qualified Data.Maybe as Mb

multiSuppressor :: Eq α => α -> [α] -> [[α]]
multiSuppressor e xs =
    let  expand e1 = if (e1 == e) then [ Just e1, Nothing ] else [ Just e1 ]
         maybes  = sequence  (map expand xs)
         res1    = map  Mb.catMaybes  maybes
    in
         -- final massaging as the whole list is normally unwanted:
         if (null xs)  then  [[]]  else  filter (/= xs) res1

关于效率的说明:

函数序列是多态的.列表中的笛卡尔积不是生命中唯一的角色.不幸的是，这碰巧会带来不幸的副作用，即如果您超出玩具大小的示例，它的内存消耗可能会变得非常大.

A note on efficiency:

Function sequence is polymorphic. Being the list cartesian product is not its sole role in life. Unfortunately, this happens to have the sad side effect that its memory consumption can become quite large if you go beyond toy-sized examples.

如果这成为问题，则可以使用以下替换代码，该代码基于KA Buhr的一个想法:

If this becomes a problem, one can use the following replacement code instead, which is based on an idea by K. A. Buhr:

cartesianProduct :: [[α]] -> [[α]]
cartesianProduct xss =
    map reverse (helper (reverse xss))
        where
            helper [] = [[]]
            helper (ys:zss) =  [y:zs | zs <- helper zss, y <- ys]

这篇关于Haskell中的字符串组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！