無駄と文化

実用的ブログ

JavaScript で割り算の商と余りを求める

JavaScript で整数同士の割り算をして商と余りを求める方法について解説します。

まず2つの整数 m, n を受け取って商と余りの組を返す関数 div を定義しましょう。

const div = (f=>(u=>u(u))(x=>f(y=>x(x)(y))))(g=>m=>n=>m>=n?(b=>b?1+g(m-n)(n)(1):g(m-n)(n)(0)):(b=>b?0:m));

はい、書けました。

試しに 14 ÷ 3 = 4 ... 2 を計算してみます。

「商: 4, 余り: 2」と正しく表示されていますね!

 

私からは以上です。

 

解説 (蛇足)

上記のコードをどのように錬成したか分かりたい人向けです。

 

まず再帰を使って普通に div を書きます。

/**
 * @param {number} m 割られる数
 * @param {number} n 割る数
 * @returns {[number, number]} 商と余りの組
 */
const div = (m, n) => {
  if (m >= n) {
    const [q, r] = div(m - n, n);
    return [1 + q, r];
  } else {
    return [0, m];
  }
}

div を実行すると div(14, 3) → [4, 2] のように2要素のタプル (配列) が返ってきます。
0番目の要素が商で、1番目の要素が余りです。

 

分割代入は Internet Explorer で動かない ので愚直なブラケット記法に書き換えます。

const div = (m, n) => {
  if (m >= n) {
    return [1 + div(m - n, n)[0], div(m - n, n)[1]];
  } else {
    return [0, m];
  }
}

ブレース {} が美しくないので if 文を三項演算子で書き換えます。

const div = (m, n) => m >= n
  ? [1 + div(m - n, n)[0], div(m - n, n)[1]]
  : [0, m];

ブラケット [] も美しくないのでタプルを三項演算子で書き換えます。

const div = (m, n) => m >= n
  ? (b => b ? 1 + div(m - n, n)(1) : div(m - n, n)(0))
  : (b => b ? 0 : m);

カリー化 🍛 します。

const div = m => n => m >= n
  ? (b => b ? 1 + div(m - n)(n)(1) : div(m - n)(n)(0))
  : (b => b ? 0 : m);

div 関数に引数 g を追加して div_ 関数に書き換えます。

const div_ = g => m => n => m >= n
  ? (b => b ? 1 + g(m - n)(n)(1) : g(m - n)(n)(0))
  : (b => b ? 0 : m);

おもむろに Z コンビネータを持ち出します。

const z = f => (u => u(u))(x => f(y => x(x)(y)));

zdiv_ をがっちゃんこします。

const div = z(div_);

これだけでは味気ないので zdiv_ をそれぞれ展開します。

const div = (f => (u => u(u))(x => f(y => x(x)(y))))(
  g => m => n => m >= n
    ? (b => b ? 1 + g(m - n)(n)(1) : g(m - n)(n)(0))
    : (b => b ? 0 : m)
);

余分なスペースや改行を取り除いてあげれば完成!

const div = (f=>(u=>u(u))(x=>f(y=>x(x)(y))))(g=>m=>n=>m>=n?(b=>b?1+g(m-n)(n)(1):g(m-n)(n)(0)):(b=>b?0:m);

いい感じですね (?)

 

解説の解説 (蛇足の蛇足)

「タプルを三項演算子で書き換える」とは?

タプルとは複数の値の組を保持しておけるデータ構造です。キーに名前が付いていない構造体 (キーを連番で管理している構造体) と見ることもできます。
(そもそも JavaScript にはタプルが無いので ['foo', 'bar'] のように配列を使っていましたが)

さて、ここで三項演算子を思い出して以下のような関数を書いてみましょう。

const f = b => b : 'foo', 'bar';

この関数 f は以下のような振る舞いをします。

f(true)   // → 'foo'
f(false)  // → 'bar'

引数に応じて 'foo' または 'bar' を返しています。
引数によって 'foo', 'bar' のどちらも返せると云うことは、関数 f は内部的に ('foo', 'bar') の組を保持しているということです。これって2要素のタプルと実質的に同じことですよね?

というわけで一般化すると、2要素 (x, y) を保持するタプルは三項演算子を使って b => b ? x : y と書けます。
要素を取り出すときは引数に true, false を渡してもいいのですが、1, 0 を渡しても同じように動作します。

const f = b => b : 'foo', 'bar';
f(1)  // → 'foo'
f(0)  // → 'bar'

 

9月の体重推移

あーもう10月ですね。
9月の体重の推移を振り返ります。

9月中の体重推移のグラフ。月初には84kgくらいだった体重が月末には78.8kgまで落ちている

8月31日から9月30日にかけて 83.7kg→78.8kg (マイナス4.9kg) という推移でした。

 

運動の記録

9月のエクササイズ時間をまとめたグラフ。9月中に70回, 累計42時間19分17秒間のエクセサイズをして、17,606kcal消費している

9月の消費は17,606kcalでした。目標通り10,000kcalを超えられてよかった。

 

9月のウォーキングの記録。34回, 累計31時間8分24秒のウォーキングで161km歩いて11,672kcal消費している

こちらはウォーキングだけを抽出した記録です。9月だけで161km歩いたらしいです。

 

前回の振り返り

先々月はこんな感じでした。

blog.mudatobunka.org

 

まとめ

今月は9月と同じくらいのペースで消費10,000kcal, ウォーキング100kmを目指せたらいいかなと思います。
体重の減りは順調なんですが、順調すぎて筋肉量まで減ってしまうとリバウンドしやすくなります。なので10月は筋トレもがんばりたい。

 

 

私からは以上です。

Rust で借用 (参照) を取り扱うときの大事な心構え

はっきり云って Rust は難しいです。

Rust は GC を持たず、 所有権という概念の上に構成されています。 そのため所有権のある値そのものを扱うより、借用 (参照) した値を扱うほうが難しくなりがちです。

なぜ借用のほうが扱いが難しいかと云うと、
所有権を持っていれば 自由に変更したり, 不要になったら破棄したり, 他の変数に所有権を移動したり できる一方で、借用は (人様のものを借りている状態なので) 可能な操作に制限がかかるからです。

 

もう一歩踏みこんで関数から借用を返そうと思うとさらに難しくなります。

借用を返す関数を書くためにはライフタイムを意識せざるを得ません。 関数スコープの中であればライフタイムを適切に推論してくれることが多いですが、スコープを超えて関数の外に借用を返そうと思うとライフタイム注釈を明示的に書かなければいけないことが増えます。

 

今回はそのように借用 (参照) を取り扱う難しさに対処するための心構えをまとめてみます。

 

借用 (参照) を取り扱うときの心構え

大事な心構え、それは「出来ないことをやろうとしない」です。

借用の取り扱いに苦しんでいるプログラマがいるとしたら、その難しさは下記の2パターンのどちらに分類できます。

  1. 原理的に不可能なことをやろうとしているので難しい
  2. 所有権やライフタイムの概念が複雑なので難しい

ここでいいニュースがあります、2のパターンには対処法があります。それは "慣れ" です。
所有権やライフタイムの概念は文章だけで説明されても真の理解に至らない傾向があります。自分でコードを書いて rust-analyzer に叱られながらリファクタリングを繰り返せば、次第に慣れて難しさが薄れるはずです。

 

さて、厄介なのは上記のパターン 1, 2 の区別がつかず、原理的に不可能なことにやろうとして時間を無駄にしてしまうことです。
この記事では原理的に不可能なことの事例を解説します。不可能であることを理解してしまえば、不必要に苦しんで時間を無駄にすることもなくなるでしょう。

 

借用して返す関数を実装してみる

と、その前に、
この記事で例示したコードは全て Rust Playground に置いてあります。

play.rust-lang.org

 

それではやっていきましょう。

 

いちばんシンプルな例

シンプルな例から始めましょう Vec<String> の各要素 String から &str を借用して返す関数を考えます。

fn borrow_strs_1(strings: &Vec<String>) -> Vec<&str> {
    let mut vec: Vec<&str> = Vec::new();
    for string in strings {
        let str: &str = string.as_str();
        vec.push(str)
    }
    vec
}

簡単ですね。
大事なのは string.as_str() の部分です。String から &str を借用しています。

 

上記の例ではライフタイム注釈を省略しました。(省略しても Rust が推論してくれるので)
が、省略せずに書くことも可能です。

fn borrow_strs_1<'a>(strings: &'a Vec<String>) -> Vec<&'a str> {
    let mut vec: Vec<&str> = Vec::new();
    for string in strings {
        let str: &str = string.as_str();
        vec.push(str)
    }
    vec
}

ライフタイム注釈 'a がところどころに付いただけで、関数本体の流れは同じですね。

さて、ここから少しずつコードを複雑にしていきましょう。

 

条件に応じて借用する

先ほどの例では Vec<String> を扱っていましたが、今度は Vec<Option<String>> を扱ってみましょう。
Some(string) からは &str を借用します。None からは何も借用できないので無視しましょう。

このようなコードになります。

fn borrow_strs_2(maybe_strings: &Vec<Option<String>>) -> Vec<&str> {
    let mut vec: Vec<&str> = Vec::new();
    for maybe_string in maybe_strings {
        if let Some(string) = maybe_string {
            let str: &str = string.as_str();
            vec.push(str);
        } else {
            // 何もしない
        }
    }
    vec
}

さきほどと大きくは変わりませんね。
if let Some(string) = maybe_string { ... } で 条件分岐して Some(string) というパターンにマッチするときだけ &str を借用しています。

 

条件に応じて代わりのものを返す

先ほどの例では要素が None のときには単に無視していました。 無視するのではなく代わりの文字列 "None": &str を返すとどうでしょう。

// None の場合には "None": &str を返す
fn borrow_strs_3(maybe_strings: &Vec<Option<String>>) -> Vec<&str> {
    let mut vec: Vec<&str> = Vec::new();
    for maybe_string in maybe_strings {
        if let Some(string) = maybe_string {
            let str: &str = string.as_str();
            vec.push(str);
        } else {
            vec.push("None");
        }
    }
    vec
}

else 節に vec.push("None"); が足されました。
この関数は狙い通りに動きます。

fn main() {
    let string1: String = "hoge".to_string();
    let string2: String = "fuga".to_string();
    let string3: String = "piyo".to_string();
    
    let maybe_strings: Vec<Option<String>> = vec![
        Some(string1), 
        None, 
        Some(string2), 
        Some(string3), 
        None,
    ];
    
    println!("{:?}", borrow_strs_3(&maybe_strings));
    // => ["hoge", "None", "fuga", "piyo", "None"]
}

ちょっと待って!

vec.push("None"); の中の "None"&str 型です。
&str も借用なのでライフタイムがあるはずです。 "None": &str のライフタイムは何になっているでしょうか?

答えは 'static です。

文字列リテラルとしてコード中にハードコードされた文字列は &'static str になります。
'static ライフタイムとはつまり、コードの実行中ずーっと生き続けるということです。

 

条件に応じて改変して返す

引数を Vec<String> に戻します。
String が長さ1文字のときは大文字に変換して &str を借用する、とするとどうでしょう。(変な要件だな)

// string が1文字なら uppercase にしてから借用したい
fn borrow_strs_4(strings: &Vec<String>) -> Vec<&str> {
    let mut vec: Vec<&str> = Vec::new();
    for string in strings {
        if string.len() == 1 {
            let str: &str = string.to_uppercase().as_str();
            vec.push(str);
        } else {
            let str: &str = string.as_str();
            vec.push(str);
        }
    }
    vec
}

借用する部分が string.to_uppercase().as_str() となっています。
大文字 (uppercase) に変換してから借用、要件そのままの実装ですね。

この関数を使うと、結果はこのようになってほしいです。

fn main() {
    let string1: String = "hoge".to_string();
    let string2: String = "a".to_string();     // "a" 1文字だけ!
    let string3: String = "piyo".to_string();

    let strings: Vec<String> = vec![string1, string2, string3];
    
    println!("{:?}", borrow_strs_4(&strings));
    // => ["hoge", "A", "piyo"]
    // と表示されてほしい...
}

...が、この関数はコンパイルできません。 下記のようなエラーが出ます。

error[E0515]: cannot return value referencing temporary value
|             let str: &str = string.to_uppercase().as_str();
|                             --------------------- temporary value created here
...
|     vec
|     ^^^ returns a value referencing data owned by the current function

エラーメッセージで「関数の中で所有されている値を参照して return することはできない」と言われています。

string.to_uppercase() はこの関数の中で生成されていて、この関数が所有権を持っています。
関数が所有権を持っている値は (値自体を return して所有権を渡さないかぎり) 関数末尾で値がドロップされてしまいます。

string.to_uppercase().as_str() のように借用して参照を関数の外に返しても、元となる値のライフタイムが関数の中に閉じているために、このような処理は認められません。

 

コンパイルが通るように修正しよう

さて、この関数を正しくコンパイルできるようにどうにか修正しようとすると...、日が暮れます。 これはいわゆる「原理的に不可能なこと」をやろうとしてしまっています。

なぜ不可能なのか?別の側面から見てみましょう。

一つ前の例で vec.push("None"); して return するのが許されたのは何故だったでしょうか?
そう、文字列リテラルで書かれた "None": &str はライフタイムが 'static なので関数の外に持ち出すことが許されたのです。

一方で string.to_uppercase() のように関数内で生成された (しかもリテラルでもない) 文字列は 'static にはなれないんですね。

 

余談ですが、string.to_uppercase() で生成した値を意図的にメモリリークさせることでライフタイムを 'static にしてコンパイルを通すことが可能です。
詳しくは下記の記事で詳しく解説しています。

blog.mudatobunka.org

 

関数内で値を生成せずに済ませる

先ほど「原理的に不可能なこと」と言い切りましたが、実は回避策があります。
関数内で生成した値の借用を返すことは不可能、ということは 値を生成せず に済ませればいいわけです。

下記のように &str を内包する enum を用意します。

#[derive(Debug)]
enum Wrapper<'a>{
    Stay(&'a str),
    Uppercase(&'a str),
}

そして関数から Vec<&str> を返す代わりに Vec<Wrapper> を返します。

fn borrow_strs_5(strings: &Vec<String>) -> Vec<Wrapper> {
    let mut vec: Vec<Wrapper> = Vec::new();
    for string in strings {
        if string.len() == 1 {
            let wrapped: Wrapper = Wrapper::Uppercase(string.as_str());
            vec.push(wrapped);
        } else {
            let wrapped: Wrapper = Wrapper::Stay(string.as_str());
            vec.push(wrapped);
        }
    }
    vec
}

if 文の then 節と else 節でそれぞれ Wrapper::Uppercase(), Wrapper::Stay() で包んでいるのが見えますね。
この関数は無事にコンパイルできて、実行してみるとこのようになります。

fn main() {
    let string1: String = "hoge".to_string();
    let string2: String = "a".to_string();     // "a" 1文字だけ!
    let string3: String = "piyo".to_string();

    let strings: Vec<String> = vec![string1, string2, string3];
    
    println!("{:?}", borrow_strs_5(&strings));
    // => [Stay("hoge"), Uppercase("a"), Stay("piyo")]
}

...はい、 "A" ではなく Uppercase("a") が印字されちゃってます。なんか全然「大文字に変換」という要件を満たしていませんね。

というわけで次に Wrapper に対して独自の Debug トレイト実装を与えます。

impl std::fmt::Debug for Wrapper<'_> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Wrapper::Stay(str)      => write!(f, "{}", str),
            Wrapper::Uppercase(str) => write!(f, "{}", str.to_uppercase()),
        }
    }
} 

このように。

すると main 関数の実行結果はこのようになります。

fn main() {
    let string1: String = "hoge".to_string();
    let string2: String = "a".to_string();
    let string3: String = "piyo".to_string();

    let strings: Vec<String> = vec![string1, string2, string3];
    
    println!("{:?}", borrow_strs_5(&strings));
    // => [hoge, A, piyo]
}

すばらしい👏

 

borrow_strs_5() では関数内で .to_uppercase() を実行していません。Wrapper で包むだけで、包んだものをそのまま Vec に詰めて返しています。
ただ包んでいるだけとはいえ、 Wrapper::Stay には「そのまま印字したい」という思いが Wrapper::Uppercase には「大文字に変換して印字したい」という思いが込められてるのがお分かりですね?

そして実際に .to_uppercase() 変換を行っているのは Debug#fmt() の中です。

 

※ この記事では流れの都合上 Debug#fmt の中でビジネスロジックに応じた実装を与えましたが、実際のコードでは Display#fmt に実装を与えたり、 Wrapper に対して独自のメソッドを実装してビジネスロジックを表現することになるでしょう

 

結局「原理的に不可能なこと」とは何だったか

今回挙げた例において、原理的に不可能なこととは結局のところ、

  • 関数内で所有権をもつ値を生成して、その値の借用を返す

ことでした。

逆に、

  • 引数からの借用をそのまま返す
  • ライフタイムが 'static な借用を返す (文字列リテラル &'static str など)
  • 引数からの借用をそのまま enum や struct に包んで返す

ことは可能で、しかも比較的簡単だということを見てきました。

上記は原理的に不可能なことを見抜くための一つのパターンに過ぎません。が、把握しておけば不可能なことに取り組んで時間を溶かすことは避けやすくなるはずです。

 

まとめ

借用 (参照) の取り扱いは繰り返しコードを書くことで慣れ、スキルとして習得できます。
ただし原理的に不可能なことをやろうとして時間を無駄にしないように気をつけてください。

「出来ないことをやろうとしない」これをどうか忘れないで。

 

 

私からは以上です。