🌊

C++とRustで純粋再帰

2025/02/22に公開

C++

Rust

scheme

tech

こんな関数を書きたいと思ったことはありませんか？

Scheme

(define (counter count)
  (lambda () 
    (display count)
    (counter (+ count 1))))

戻り値にクロージャーを置いて、関数を呼び出す度に引数の値を更新していく擬似的な再帰です
お手軽に反復カウンターが実装できる便利な関数ですが、戻り値の型は

counter:int->(int->(int->...)->...)

と無限ループしてしまい、静的型付けでは容易に実装できません
型がループするような戻り値の実装には、クロージャーの抽象化が必須です
例えばC#ではDelegate型へのアップキャストでこれを実現します

using System;
					
public class Program
{
    public static void Main()
    {
        Delegate func=MakeFunc();
		
        for(int i=0;i<5;++i)
        func=((Func<Delegate>)func)();
    }

    static Func<Delegate> MakeFunc(int count=0){
        return delegate{
            Console.WriteLine(count);
            return MakeFunc(count+1);
        };
    }
}

しかし言語によっては関数とクロージャーの型が厳密に分かれていることもあります
例えばC++とRustにはDelegateのような便利な基底型はありません

構造体を使う

そこで便利なのが構造体です
特にRustは通常の再帰関数にも構造体を用いるようです
ここでは関数を保持する構造体を考えることで、この構造体を戻り値としたクロージャーを考えます
それぞれの実装は以下です

C++

#include <iostream>
#include <functional>

const int START_COUNT=0;

struct func_obj{
    std::function<struct func_obj (void)> func;
};

struct func_obj make_func(const int count=START_COUNT){
    return func_obj{[count]->struct func_obj{
            std::cout<<count<<std::endl;
            struct func_obj func=make_func(count+1);
            return func;
	}};
}

int main(void){
    func_obj test=make_func();

    for(int i=0;i<5;++i)
        test=test.func();
};

Rust

fn main(){
    let mut func_obj:Func=make_func(0);
	
    for i in [0; 5]{
        func_obj=(func_obj.func)();
    }
}

struct Func{
    func:Box::<dyn Fn::()->Func>
}

fn make_func(count:i8)->Func{
    Func{
        func:Box::new(move ||{
            println!("{}",count);
            make_func(count+1)
        })
    }
}

こういう関数が単純に実装できるのは動的型付けの強みですが、型の恩恵にも授かれるので、構造体は積極的に活用していきたいですね

構造体を使う

Discussion