[初心者]else文でなぜrestが出てくるのかわからないです Ocaml

Question

○前提・実現したいこと
プログラミングの基礎という初心者向けのOcamlの教材でメトロネットワークを作る問題をしていたのですが理解できないところがあります。

駅間リストのデータから情報を取り出す関数　get_ekikan_kyori　を作り、駅名を二つ受け取ってその間の距離を返すというものです。

get_ekikan_kyori "茗荷谷" "新大塚" global_ekikan_list

で　1.2 を返すなどです。　直接繋がっていない時にはinfinityを返します。

type ekikan_t = { 
  kiten  : string; (* 起点 *) 
  shuten : string; (* 終点 *) 
  keiyu  : string; (* 経由路線名 *) 
  kyori  : float;  (* 距離 *) 
  jikan  : int;    (* 所要時間 *) 
} 
let global_ekikan_list = [ 
{kiten="代々木上原"; shuten="代々木公園"; keiyu="千代田線"; kyori=1.0; jikan=2}; 
{kiten="代々木公園"; shuten="明治神宮前"; keiyu="千代田線"; kyori=1.2; jikan=2}; 
{kiten="明治神宮前"; shuten="表参道"; keiyu="千代田線"; kyori=0.9; jikan=2}; 
{kiten="表参道"; shuten="乃木坂"; keiyu="千代田線"; kyori=1.4; jikan=3}; 
{kiten="乃木坂"; shuten="赤坂"; keiyu="千代田線"; kyori=1.1; jikan=2}; 
{kiten="赤坂"; shuten="国会議事堂前"; keiyu="千代田線"; kyori=0.8; jikan=1}; 
{kiten="国会議事堂前"; shuten="霞ヶ関"; keiyu="千代田線"; kyori=0.7; jikan=1};

let rec get_ekikan_kyori eki1 eki2 lst = match lst with
  [] -> infinity
 | {kiten = k; shuten = s; keiyu = y; kyori = r; jikan = j} :: rest ->
    if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)
    then r
    else get_ekikan_kyori eki1 eki2 rest

(* テスト *) 
let test1 = get_ekikan_kyori "茗荷谷" "新大塚" global_ekikan_list = 1.2 
let test2 = get_ekikan_kyori "茗荷谷" "池袋" global_ekikan_list = infinity 
let test3 = get_ekikan_kyori "東京" "大手町" global_ekikan_list = 0.6 

パターンマッチを使うときは先頭のリストと残りのリストに分けてfirstとrestというパターン変数を使ってアクセスするらしいです。

片方の距離だけなので駅１が始点と終点でif (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)、
then rで距離を返すのは分かるのですが、なぜelseでrestが出てくるのかがわからないです。
それとパターンマッチでfirstではなく{kiten = k; shuten = s; keiyu = y; kyori = r; jikan = j}を代わりに使ってる理由も教えていただきです。
そもそもなぜ、リストは、first(最初の要素) とrest(その残りの要素)に分けているのでしょうか？

どなたかご存知の方教えていただけたら助かります、、、

Answer 1

パターンマッチを使うときは先頭のリストと残りのリストに分けてfirstとrestというパターン変数を使ってアクセスするらしいです。

なんだか「そういう決まり」というように思っていそうですが、別にそんなことはないです。

なぜelseでrestが出てくるのかがわからないです。

リストの先頭が調べたい駅間データなのかを判定して、
そうだったらその駅間データの距離を返して、
違ったらリストの残りに対して同じ処理をする、という作りのプログラムだからです。

それとパターンマッチでfirstではなく{kiten = k; shuten = s; keiyu = y; kyori = r; jikan = j}を代わりに使ってる理由も教えていただきです。

別にfirst::restと書いてもいいです。
その場合eki1=first.kitenなどとなるだけです。

そもそもなぜ、リストは、first(最初の要素) とrest(その残りの要素)に分けているのでしょうか？

リストの先頭が調べたい駅間データなのかを判定して、
そうだったらその駅間データの距離を返して、
違ったらリストの残りに対して同じ処理をする、という作りのプログラムだからです。

---

コメントに対する追記

先頭の要素と残りの要素というのは先頭がkiten="代々木上原"; shuten="代々木公園"; keiyu="千代田線"; kyori=1.0; jikan=2};で、残りの要素が{kiten="代々木公園"; shuten="明治神宮前"; keiyu="千代田線"; kyori=1.2; jikan=2};からそれ以降全部ということなんでしょうか？

global_ekikan_listに対して言えばそうです。

再帰関数は処理が出来上がっている前提で使う関数？だと思うのですが

何を言っているのかわかりません。

なぜ　then r　のところにはget_ekikan_kyori　を使っていなくelseの方だけ使っているのでしょうか？

使う必要がどこにあるのです?

if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)　は何をしているのか教えていただけないでしょうか？

(eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)かどうかを判定しています。

---

リストlstにxがあるかないかを返す関数isExistを似たようなアルゴリズムで書いてみました。

let rec isExist x lst = match lst with
	[] -> false
	| first :: rest ->
		if x = first then true
		else isExist x rest;
		
isExist 5 [1;2;3;4;5]; (* true *)
isExist 5 [1;2]; (* false *)

Comments

[ryuuabis]

返信ありがとうございます。データを取り出すプログラムということなんですね。。

すみません、先頭の要素と残りの要素というのは先頭がkiten="代々木上原"; shuten="代々木公園"; keiyu="千代田線"; kyori=1.0; jikan=2};で、残りの要素が{kiten="代々木公園"; shuten="明治神宮前"; keiyu="千代田線"; kyori=1.2; jikan=2};からそれ以降全部ということなんでしょうか？

それと再帰関数は処理が出来上がっている前提で使う関数？だと思うのですがなぜ　then r　のところにはget_ekikan_kyori　を使っていなくelseの方だけ使っているのでしょうか？

すみませんそれと if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)　は何をしているのか教えていただけないでしょうか？

沢山の追加質問すみません、、
教えていただけたら助かります。。

[ozwk]

追記しました

[ryuuabis]

分かりにくい質問ですみません。。
first::restの説明分かりました、ありがとうございます。

再帰関数ということはget_ekikan_kyoriという関数の処理の中でまたget_ekikan_kyoriという関数を使える（elseで使っているみたいに）と思うのですが、if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)を判定してその通りだったらthenでget_ekikan_kyori eki1 eki2みたいに使うべきじゃないのでしょうか。
get_ekikan_kyori自体がリストの先頭が調べたい駅間データなのかを判定して、
そうだったらその駅間データの距離を返して、違ったらリストの残りに対して同じ処理をする、という作りのプログラムだとしたら、なぜにif (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)を判定して違った場合のelseで使っているのでしょうか。
判定して違ったらinfinityだったり空リストを返すものじゃないのでしょうか、、？

[ryuuabis]

正解はこうなっていますが、
let rec get_ekikan_kyori eki1 eki2 lst = match lst with
[] -> infinity
| {kiten = k; shuten = s; keiyu = y; kyori = r; jikan = j} :: rest ->
if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)
then r
else get_ekikan_kyori eki1 eki2 rest

こうか、
let rec get_ekikan_kyori eki1 eki2 lst = match lst with
[] -> infinity
| {kiten = k; shuten = s; keiyu = y; kyori = r; jikan = j} :: rest ->
if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)
then r
else r rest

こうになるイメージなのですが
let rec get_ekikan_kyori eki1 eki2 lst = match lst with
[] -> infinity
| {kiten = k; shuten = s; keiyu = y; kyori = r; jikan = j} :: rest ->
if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)
then get_ekikan_kyori eki1 eki2
else get_ekikan_kyori eki1 eki2 rest

なぜ一番上のようなプログラムになっているのでしょうか、、

[ozwk]

> get_ekikan_kyori自体がリストの先頭が調べたい駅間データなのかを判定して、
そうだったらその駅間データの距離を返して、違ったらリストの残りに対して同じ処理をする、という作りのプログラムだとしたら、なぜにif (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)を判定して違った場合のelseで使っているのでしょうか。
判定して違ったらinfinityだったり空リストを返すものじゃないのでしょうか、、？

「違ったらリストの残りに対して同じ処理をする」のですから
「違ったらinfinityだったり空リストを返す」のではおかしいでしょう。

[ozwk]

> 再帰関数ということはget_ekikan_kyoriという関数の処理の中でまたget_ekikan_kyoriという関数を使える（elseで使っているみたいに）と思うのですが、

はい。使えます。

> if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k)を判定してその通りだったらthenでget_ekikan_kyori eki1 eki2みたいに使うべきじゃないのでしょうか。

なぜ?
if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k) は先頭要素が目的のものだったらthenですよ?
ひょっとして逆だと思ってます?

[ozwk]

> else r rest

r は float で restはekikan_t listですから r rest は floatという関数でないものにekikan_t listを渡そうとしていて意味わからんでしょう。

> get_ekikan_kyori eki1 eki2

get_ekikan_kyori が返したいのはfloatですが
その返り値をget_ekikan_kyori eki1 eki2としたら ekikan_t list-> floatで型が合ってません。

[ryuuabis]

if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k) で判定して　thenはfirst 、
else はrest についての処理を書くという認識でよろしいでしょうか？

関数の中の処理に使える再帰関数のget_ekikan_kyoriはfirstのthenでは使えず、
restのelstしか使えないということでしょうか？

同じ型の関数しか渡せないということでしょうか、
ということは参考に書いていただいたアルゴリズムの、else isExist x rest;　は
自動的にrestなど全てbool型に変換されているということでしょうか？

[ozwk]

> if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k) で判定して　thenはfirst 、
else はrest についての処理を書くという認識でよろしいでしょうか？

なんだかそう書かなければいけないみたいな言い方が気になりますが、
とりあえず今回はそう書いているということです。

> 関数の中の処理に使える再帰関数のget_ekikan_kyoriはfirstのthenでは使えず、
restのelstしか使えないということでしょうか？

別に文法上は使っても問題ありません。

> 同じ型の関数しか渡せないということでしょうか、
ということは参考に書いていただいたアルゴリズムの、else isExist x rest;　は
自動的にrestなど全てbool型に変換されているということでしょうか？

いいえ、変換などしていません。

isExistは 'a -> 'a list -> bool 型ですから (isExist x rest)はbool型です

[ozwk]

isExistに関して説明すれば

「リストからとある値があるかどうかを判定する操作」とは
リストが空であれば、返り値は「なかった」となる。
リストが空でなければ、返り値は、
先頭要素が「とある値」であれば、「あった」となる。
そうでなければ残りのリストに対して「リストからとある値があるかどうかを判定する操作」を行った結果となる。

まずプログラム抜きにこの手順で探せることを理解しないといけません。

[ryuuabis]

そうでなければ残りのリストに対して「リストからとある値があるかどうかを判定する操作」を行った結果となる。とは、それ以前のリストが空であれば、返り値は「なかった」となる。
リストが空でなければ、返り値は、
先頭要素が「とある値」であれば、「あった」となる。の処理を繰り返すということなんですね。なるほどです。。

すみません、まずプログラム抜きにこの手順で探せることを理解しないといけません。　、とは関数のisExistを使わずに探したりできるという意味でしょうか？

すみませんそれと、isExistは 'a -> 'a list -> bool 型ですから (isExist x rest)はbool型　の'a -> 'a list -> bool 型は処理の結果の一連の流れの型みたいなことでしょうか。型がどんどん変わっていっているということなんでしょうか、
それともaはx, a listはlist , 最後のboolはfalseを書いているからOcamlが自動的にboolと判断して最終的にbool型と自分で理解していくということでしょうか？

[ozwk]

> プログラム抜き

純粋なアルゴリズムの話です。例えば人間に指示してやらせるなど

> すみませんそれと、isExistは 'a -> 'a list -> bool 型ですから ...

`aを受け取って`a listを受け取ってboolを返す関数型という意味です
(正確には`aを受け取って「`a listを受け取ってboolを返す関数」を返す関数型)

なんの教材を使っているかはわかりませんが、基本的なことなので多分最初の方に出てくるはず...
Ocamlは型をあまり明示しないから出てこなくても不思議ではないですが。

[ozwk]

「プログラミングの基礎」という本なのですね。
目次を見た限り4章ぐらいからやり直したほうが良さそうです

[ryuuabis]

なるほど、型の最後は返すという意味なのですね。

そうですね、理解できてないので復習とアルゴリズム自体の勉強もしたいと思います。。
ここまで分かりやすく説明していただきとても助かりました、、！
ありがとうございましたm(__)m