在SML中反转字符串的想法

Question

我是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));

Answer 1

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

val reverseString = implode o rev o explode;

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