recursion - ネストされたリストをパターンマッチする方法は?

Question

sml/nj で、空でないリストのリストを取得し、それらの各空でないリストの最初の要素のリストを返す関数を作成したいと考えています。

fun get_first [] = []
 | get_first x::xs = (hd x)::get_first xs;
get_first: ('a list) list -> 'a list;

しかし、これは機能していません...誰かが間違っていることを知っていますか?

Answer 1

x::xs次のように、リストパターンを括弧で囲むのを忘れています。

fun get_first [] = []
  | get_first (x::xs) = (hd x)::get_first xs

それが機能しない理由は少し「複雑」です。SMLでは、リストはデータ型といくつかのシンタックスシュガーとして定義されています。基本的にはこんな感じ

datatype 'a list = nil | :: of ('a * 'a list)

データ型コンストラクターでパターンマッチングを行うことができるため、nil（通常は[]と書く）との両方に対してパターンマッチングを行うことができます::。
ただし、括弧を付けない場合は、関数が3つのカレー引数にパターンマッチングされているかのように解釈されます。これはおそらくこのように視覚化された方が良いでしょう

  | get_first (x) (::) (xs) = ....

また、map関数を使用してこれを簡単に実装できることにも注意してください

fun get_first xs = map hd xs