第27回 オフラインリアルタイムどう書くの問題「分岐と行き止まり」をRustで解く

オフラインリアルタイムどう書くの過去問題「分岐と行き止まり」を、Rust(rustc 1.0.0-nightly (2fc8b1e7c 2015-03-07) (built 2015-03-07))で解きました。(他の言語での回答はこちら)

Rustの感想

• Rustは関数型プログラミングには向いてない、と思ったが、勘違いだった。やればできる。
• やればできるのだが(後述)、iter(),into_iter()とcollect::<>()だらけのこれが関数型と呼べるのか、関数型プログラミングの成立条件には、簡潔さというものは必須条件なのではないか? あるいはiter()とcollect()は慣れると見えなくなるのか。
• ただ、ライブラリの作りとしては関数型プログラミングの道具立はそろえられている。flat_mapしかり、zip, fold, fuse, ..。
• ちなみに、iter(),into_iter()はコレクション(Vec,..)をイテレータに変換、collect()はその逆。
• mapやfilterなどの処理は、イテレータ上で行う(Java8のstreamみたいなもんですね)。
• iter()は繰り返し要素がborrowing(&, ポインタ参照)でわたってくる。
• into_iterは値渡しで、(Copy traitをderiveしてなければ)ムーブセマンティクス。
• rustcのエラーメッセージは丁寧ですばらしい、賞賛すべきレベル。学習者にとっては、このエラーメッセージが死活的に重要。エラーメッセージがこれほど丁寧でなれば、このレベルのプログラムでも絶対書けなかった(断言)。
• 今でもRustはどんどん変更されている。さすがにbreaking changeの頻度は少なくなっていると思うが、この程度のプログラムでも影響のある変更は結構ある。エラーメッセージがわかりやすくなってたりもするので、できるかぎりnightlyを追うべし。

Rustが関数型プログラミングに向いてないと思った理由と、乗り越えるための対策

• コレクションライブラリが破壊的操作ベース(sort,dedup)
• (対策) → BTreeSetを使う
• 文字列操作も同じく破壊的操作ベース。結合するのにpush_str()とか。破壊的以前に煩雑で死ぬ。
• (対策) → format!()マクロを多用。
• 式中の関数返り値はその場だけのテンポラリなライフタイムなので、直接・間接に後でも使う場合、ローカル変数に保存してライフタイムで延長することで回避するしかないかと思った。
• (対策) → into_iter()でムーブセマンティクスにすることで回避。値渡しがRustの基本であると心に刻む。
• (クロージャにmove接頭辞を付ける(move |a| ..)のも関係がありそうだが、どういうときに使うのだろうか謎)
• collectは多相だが、どんな型を返したいのかを示せる型情報が引数やselfでは与えられないため、多相性の解決を代入先の変数の型で指定するしかないのでは。
• (対策)→collect::<Vec<String>>()みたいに型アノテーションを使用できる。このとき、「collect::<Vec<_>>()」のように要素の型は指定しなくても推論されるようだ。

コード

/*
http://nabetani.sakura.ne.jp/hena/ord27raswi/
*/
#![feature(collections)]
#![feature(core)]

extern crate core;
use std::string::String;
use std::collections::BTreeSet;
use core::iter::FromIterator;

static PATHS:[(char, char);21]
    = [('1','a'),('1','g'),('2','d'),('2','h'),
       ('3','b'),('3','f'),('a','b'),('b','5'),
       ('b','c'),('c','4'),('c','6'),('d','c'),
       ('d','e'),('e','5'),('f','g'),('g','c'),
       ('g','e'),('g','h'),('h','4'),('h','i'),
       ('i','6')];
 
fn traverse(node:char, stopper:&str) -> Vec<String> {
    if stopper.contains(node) {
        vec![]
    }
    else if node == '4' || node == '5' || node == '6' {
        vec![format!("{}", node)]
    }
    else {
        PATHS
            .iter()
            .filter(|&&(beg,_)|{beg==node})
            .flat_map(|&(_,end)|traverse(end, stopper).into_iter())
            .collect()
    }
}

fn solve(stopper:&str) -> Vec<String> {
    BTreeSet::from_iter(
        ['1','2','3']
            .iter()
            .flat_map(|start_point|
                      traverse(*start_point, stopper)
                      .iter()
                      .map(|end_point| format!("{}{}", *start_point, end_point))
                      .collect::<Vec<String>>()
                      .into_iter()
                      )).into_iter().collect::<Vec<String>>()
}

fn test(stopper: &str, expected: &str) {
    let mut answer = solve(stopper)
        .iter()
        .map(|s| s.as_slice())
        .collect::<Vec<&str>>().connect(",");
    if answer == "" {
        answer = String::from_str("-");
    }
    assert_eq!(answer, expected);
}

fn main() {
/*0*/ test( "befi", "14,16,24,26" );    
/*1*/ test( "abc", "14,15,16,24,25,26,34,35,36" );    
/*2*/ test( "de", "14,15,16,24,26,34,35,36" );    
/*3*/ test( "fghi", "14,15,16,24,25,26,34,35,36" );    
/*4*/ test( "abcdefghi", "-" );    
/*5*/ test( "ag", "24,25,26,34,35,36" );    
/*6*/ test( "dh", "14,15,16,34,35,36" );    
/*7*/ test( "bf", "14,15,16,24,25,26" );    
/*8*/ test( "ch", "15,25,35" );    
/*9*/ test( "be", "14,16,24,26,34,36" );    
/*10*/ test( "ci", "14,15,24,25,34,35" );    
/*11*/ test( "cgi", "15,24,25,35" );    
/*12*/ test( "acgi", "24,25,35" );    
/*13*/ test( "cdefghi", "15,35" );    
/*14*/ test( "acdefghi", "35" );    
/*15*/ test( "cdegi", "15,24,35" );    
/*16*/ test( "bcdegi", "24" );    
/*17*/ test( "afh", "14,15,16,24,25,26,34,35,36" );    
/*18*/ test( "abfh", "14,15,16,24,25,26" );    
/*19*/ test( "dfh", "14,15,16,34,35,36" );    
/*20*/ test( "cdfh", "15,35" );    
/*21*/ test( "deh", "14,15,16,34,35,36" );    
/*22*/ test( "cdeh", "15,35" );    
/*23*/ test( "abefgh", "24,26" );    
/*24*/ test( "abdefgh", "-" );    
/*25*/ test( "acfghi", "25,35" );    
/*26*/ test( "acdfghi", "35" );    
/*27*/ test( "cegi", "15,24,35" );    
/*28*/ test( "abcfhi", "15,25" );    
/*29*/ test( "abcefhi", "-" );    
/*30*/ test( "abdi", "14,15,16,24,34,35,36" );    
/*31*/ test( "abdfi", "14,15,16,24" );    
/*32*/ test( "bdi", "14,15,16,24,34,35,36" );    
/*33*/ test( "bdfi", "14,15,16,24" );    
/*34*/ test( "adfh", "14,15,16,34,35,36" );    
/*35*/ test( "adfgh", "34,35,36" );    
/*36*/ test( "acdfhi", "15,35" );    
/*37*/ test( "bcdfgi", "24" );    
/*38*/ test( "bcdfghi", "-" );    
/*39*/ test( "defi", "14,15,16,24,34,35,36" );    
/*40*/ test( "defhi", "14,15,16,34,35,36" );    
/*41*/ test( "cdefg", "15,24,26,35" );    
/*42*/ test( "cdefgi", "15,24,35" );    
/*43*/ test( "bdefg", "24,26" );    
/*44*/ test( "bdefgi", "24" );    
}