首页 文章

在SML中反转字符串的想法

提问于
浏览
1

我对SML很新,并且有一些C / C背景 . 我一直在尝试编写一个名为reverseString的函数,它接收一个字符串来反转 . 非常直截了当 . 使用辅助函数,我能够编写一个函数来反转任何给定的字符串,并在结果中添加一个额外的字符 . 例如:

- reverseString("hello");
val it = "ollehh" : string

任何有关如何克服这一障碍的帮助都将非常有帮助 . 请记住,我正在尝试在没有任何附加功能的情况下实现该功能(即,在我的实现中没有使用的功能):

fun reverseAux(s:string, i:int) : string = 
    if i = 0 then str(String.sub(s, 0)) 
    else str(String.sub(s, i-1)) ^ reverseAux(s, i-1);

fun reverseString(s:string) : string = 
    reverseAux(s, size(s));

3 回答

  • 3

    除了我的评论之外,一旦您了解了模式匹配,这是一个更简单的解决方案:

    fun helper [] = []
    | helper [x] = [x]
    | helper (l::ls) = (helper ls) @ [l];
    
    fun reverse s = implode (helper (explode s));
    

    explodeimplode 是分别将 string 转换为 char list 的函数,反之亦然 . 列表比字符串更容易遍历 .

  • 1

    接受的答案(值得接受)解释了你如何从头开始 - 这是一个很好的想法,当你开始时,但它涉及 @ 这是一个有点昂贵的操作(见this的一个很好的讨论如何看似线性的算法在引擎盖下可以是二次的 . 有一种方法可以避免它,虽然解释它有点涉及(谷歌"tail recursive reverse",如果你感兴趣) . 相反,内置函数 rev 已经实现了有效的列表反转 . 使用它和内置合成运算符 o 可以允许在一行中创建 reverseString

    val reverseString = implode o rev o explode;
    

    请注意,我使用 val 而不是 fun . 组合是一个更高阶函数,它返回其他函数,我使用组合直接创建我想要的函数,而不是从头开始定义它 . 将大量代码打包到单行代码中的能力是函数式编程的主要优势之一 . 在这种情况下,它使用该组合是一个链接操作符,并从右到左阅读 . 它说要反转一个字符串你应该首先将它爆炸成一个列表,然后反转电梯,然后将其内爆回一个字符串 .

  • 6

    你可以爆炸,然后折叠,然后内爆:

    fun reverse s = implode (foldl op:: [] (explode s));
    

相关问题