関数型言語コミュの[Haskell]初学者の質問

趣味でHaskellを勉強中のものです。
チュートリアル「A Gentle Introduction to Haskell」には、こんな関数の例が出てきます。

length [] = 0
length (x:xs) = 1 + length xs

ここでxはアトムで。xsはリストにマッチ(ユニフィケーション?)するということで「xは最初の要素に束縛され、xsはリストののこりの部分に束縛されます」という説明文が書いてあります。
ここで例えば、なぜ「xがリスト、xsが最後の要素」に束縛されたりすることがないと保証されるのでしょうか。こんな初歩の所からつまづいて申し訳ありませんがどなたか解説頂けますと幸いです。

コメント(34)

最初
全て
最新の40件

[1] mixiユーザー 04月29日 21:39

そういう仕様だからとしか・・・。

C 風に言うなら、

typedef struct List List;
struct List {
　type value;　/* このノードの値 */
　List* next;　/* 次のノード */
};

の、value と next に分離してるだけです。

[2] mixiユーザー 04月29日 21:55

保証といわれれば、確かにそういう仕様だからになるかも。
あとは、まぁ':'は1:[2,3,4] = [1,2,3,4]っていう風になる
演算子だから、その対応にのっとってバインドされるんだと
理解してもいいと思います。

[4] mixiユーザー 04月30日 02:25

みなさま初歩以前の質問にも暖かくコメントを頂きありがとうございます。とりあえず「仕様だから」って事で自分を納得させて先に進みたいと思います。その途上で何かを発見できたらそのつど御報告させて頂きたいと思っております。
重ねてありがとうございました。

[5] mixiユーザー 04月30日 03:33

hugs か ghci 上で、
> 1:[2,3]
> [1,2]:3
とそれぞれ打ってみてください。

あと、
> :t (:)
とすれば、":"という演算子の型が調べられるので、これも参考になるかもしれません。

[6] mixiユーザー 04月30日 03:59

5: たけをさん
当方はGHC6.4.1なのでghci使ってみましたが、眼からウロコが落ちましたです(おおげさ)。そうか「:」演算子はスカラーを第一引数、リストを第二引数にとってconsしたのを返すという仕様だという事なのですね(こういう理解で良いでしょうか？)。大変良く納得できました。Haskellの勉強が楽しくなりそうです。これからも色々煩わせるかと思いますが、おひまで物好きな方だけで結構ですからお付き合い頂けますと幸いです。

[7] mixiユーザー 04月30日 06:46

cons 1 (cons 2, []) -> [1,2]
: はただ単にconsのsyntactic sugarです。

x:xsと書くと:はListのheadとtailのパターンマッチになります。
（質問の的外れ答えならごめんなさい）

[8] mixiユーザー 05月01日 16:59

関数型言語における「リスト」というのは、C言語などでいう「リスト」とは少し違います。

C言語などでは、単なる配列の別実装としてのリストですが、Haskell,Lisp系などの言語では、リストは（少なくとも概念上は）「再帰的なcons」というものになります。
「cons」とは、要はペアで、ペアを使ってリストが作られています。ペアを(A . B)と表せば、
[A,B,C,D]というリストは、
(A . (B . (C . (D . NULL))))
というものになります。つまり、Aが最初の要素で、リスト全体は「Aと残りのリストのcons」となります。

なんでそんなことになってるのかというのは、使っていくと利便性がだんだんわかっていくと思います。
で、以上のような定義になっているので、ご質問のような心配は杞憂だと思います。

[9] mixiユーザー 05月03日 05:51

皆様コメント大変ありがとうございます。最初に質問を発した者です。大変感謝しております。

8: ふくださん
＞関数型言語における「リスト」というのは、C言語などでいう「リスト」とは少し違います。
例えばLispにおける「リスト」を思い浮かべれば良いのでしょうか?(Lispは昔、当時NTTにいた竹内郁生先生の本でちょっとだけ勉強した事があります)

いいわけをしますと、
(A (B (C (D (E nil))))
みたいな表記法のリストだと、(A X)とパターンマッチさせたときに「Xはリストだ」と直感的に理解できます。
一方初学者にはとっつきやすい
[1,2,3,4,5]
形式ですと、これと[x:xs]をパターンマッチさせたときに「xsがリストだ」とは自明ではないのではないか、と考えたのが出発点です。表記法としてどっちが嬉しいかと言うと断然Haskell方式なのですが、私みたいに勘違いをする元にもなるわけですね。
以上、ゴミでした。

[10] mixiユーザー 05月03日 06:36

>例えばLispにおける「リスト」を思い浮かべれば良いのでしょうか?
まさにそのとおりです。

[11] mixiユーザー 06月18日 17:08

Haskell本どんなのがお勧めですか？
アマゾンで見たけど手頃なのがなかったです
そんなに初等的でなく、難しすぎないのが
いいのですが　できればサンプルCD
　処理系つきのがいいです
よろしくおねがいします

[12] mixiユーザー 06月18日 17:58

ふつうのHaskellプログラミング
http://mixi.jp/view_item.pl?id=512986
こちらは、比較的オススメだと思います。
処理系は付属していませんが。

入門Haskell
http://mixi.jp/view_item.pl?id=448487
こちらは、オススメしません。

処理系は、Hugs98をオススメします。
http://www.haskell.org/hugs/

Webで入門では、こちらをオススメします。
http://web.archive.org/web/20030814121222/http://www.teu.ac.jp/kougi/koshida/Prog6/index.html

[13] mixiユーザー 06月18日 18:22

ゆーあいさん
ありがとうございます　早速アマゾンで
ふつうのHaskellプログラミング
注文しました

[15] mixiユーザー 06月18日 19:21

もう注文されたとは、ビックリしました。
私は、極力本屋で一度読んでからしか買わない人間なので。

ですから一様私も本屋で一通りは読みましたが
ちゃんとは見ていません。
それに私はMonadを使いこなせるまでは至っていないので
私が書かなかった方が良かったかもしれません。

入門Haskellをススメナイ理由は、いきなりGHCの導入と
最初のハードルが高いことです。
でも機会があれば読んでみることをオススメします。

こちらも有名なHaskell関連のページですのでオススメします。
http://www.sampou.org/

[16] mixiユーザー 06月19日 10:02

いや「ふつうのHaskellプログラミング」でも割とすぐGHCのインストールの話になります。どちらの本も処理系CDのようなものはついていません、何処からかダウンロードしてのインストールを勧めています。
「入門Haskell」には MacOSX へのインストールの話しも書いてあります。

[18] mixiユーザー 06月21日 00:47

「ふつうのHaskellプログラミング」(ふつける)ではMacOSXでのインストールの話は明示されていませんが、「インストーラを使いましょう」と書いてあります。

MacOSXでもGHCのインストーラは(最新版ではないにせよ)用意されていますので、そのあたりで書籍の評価はできないと思います。だいたいインストール本ではないのだし。

私は「入門Haskell」もふつけるも買いました。以下の2点を目論んだからです。(1)同じことが別の著者によって言い換えられて、理解が深まるかもしれない(2) 2冊あれば、どちらかに書いていないことももう一方で相補されるかもしれない

[19] mixiユーザー 08月09日 00:40

圏論とHaskellのつながりが掴めない
モナド則と圏論を数学書と見比べてみても
どこが同じなのかわからない

[21] mixiユーザー 08月22日 09:34

Visual Haskell インストールしましたが
使い方がわかりません
ドキュメントみると .Netが必要とありましたが
.slnとか見当たらないし
.Netは入ってます

なんかHaskell のソースにブレークポイント
はってステップ実行とかできるんですか？

[23] mixiユーザー 08月29日 21:09

私自身良く判らないので、こちらを見てみてはどうでしょうか？
http://www.sampou.org/haskell/a-a-monads/html/monadfns.html

[25] mixiユーザー 10月06日 09:51

以下のコーディングについてです

primes = [ p | (p:_) <- iterate sieve [2..]]
sieve(p:ps) = [x| x<-ps, mod x p /=0]

x<-psの ps は何を指してるんですか？　

[26] mixiユーザー 10月06日 13:41

その ps は sieve の引数です。
たとえば、[2,3..] のようなリストを考えると、 p は2、psは[3,4..] です。
リスト内包表記なので、 x には ps の要素が1つずつ順番に入り、 x を p で割った余りがゼロだと除外して、それ以外のものから構成されるリストを作る。つまり、 ps から p の倍数を取り除いたリストを sieve は返します。 [2,3..] なら [3,5..] という奇数列になります。

で、これを iterate で繰り返すと素数が出てくる。
やっていることは本質的にはエラトステネスの篩なので sieve という名前が使われています。

[27] mixiユーザー 10月06日 18:27

ナルホドです
ありがとうございます
iterate は[2..]の無限リストの先頭
要素を順番に取り出してるということ
ですか？

[28] mixiユーザー 10月06日 20:46

iterate f x = x : f x : f (f x) : f (f (f x)) : ...
という無限リストです。ですから iterate sieve [2..] は、
[2..] : [3,5..] : [5,7,11, ] : [7,11, ]
のようになります(sieveを何度も適用するので、最初は2の倍数が取り除かれ、次に3の倍数が、次に5の倍数が……という風に取り除かれていく)。
先頭要素だけ取り出しているのは、その iterate を取り囲む内包表記の役割です。

[29] mixiユーザー 01月02日 22:01

「ふつうのHaskellプログラミング」を読んで勉強しているのですが、
firstNLines n = unlines . take n . lines
を完全なポイントフリースタイルにするには高度な手段が必要と書いてあったのですが、実際どう書き換えればnが消えるのでしょうか？
どなたかご存じでしたら教えていただけないでしょうか。

[30] mixiユーザー 01月02日 23:21

unlines . take n . lines
(unlines . take n) . lines
(. lines) (unlines . take n)
(. lines) ((unlines .) (take n))
((. lines) . (unlines .)) (take n)
((. lines) . (unlines .)) . take
(. lines) . (unlines .) . take

(.) は単なる演算子であることとセクションを思い出せば、あとは慣れです。
もっとも、この表記がわかりやすいかどうかは疑問ですが。

[31] mixiユーザー 01月03日 09:36

セクションと聞いてなんとなくわかりました。

(+)などのように、左側を渡してないセクションとか右側を渡していないセクションを考えていけばいいわけですね。

ありがとうございました。

[33] mixiユーザー 11月27日 09:17

やぎさんの疑問は、「副作用」とは何か、をきちんと定義しないまま考えようとしてるからじゃないかな、と思います。

モナドは副作用を扱ういくつもある手段のうちのひとつなので、とりあえず脇に置いておきましょう。モナドそのものと副作用とはあんまり関係ありません。

純粋関数型言語の「純粋」が意味するところの「副作用がない」は、「参照透明である」ということです。式の効果は、陽に与えられた入力と、そこからの戻り値のみによって決まり、入力が同じなら結果も常に同じ。

で、入出力は副作用かどうか、というのは、実は見方によります。入出力をプログラムと切り離した外部の世界ものと考えると、何かを出力させるという式は、同じ入力でも何回実行するかによって効果が異なるので、参照透明になりません。

けれども、出力を受け取る「世界」そのものをあるオブジェクトで表現して、出力関数の引数と戻り値にしてやったら? 例えば puts :: String -> World -> World みたいに。この場合、2回何かを出力するというのは (適当な擬似言語で書きます):

world1 = puts("hello", world0)
world2 = puts("hello", world1)

となり、world1とworld2は状態が異なるので (world1は"hello"を一回見た世界、world2は"hello"を二回見た世界)、参照透明性は崩れません。

このままだと、world3 = puts("bye", world1) のようにすると、world3は"hello" "bye" を見た世界、ということでworld2とは一種のパラレルワールドになります。あるいは世界を一度world1まで巻き戻してから別の世界へと進んだとも言えます。外の世界がコンピュータシミュレーションならそれも可能なんですが、外の世界が現実だと巻き戻すことはできません。そこで、「世界の状態は一回しか使えない」というような仕組みを別途用意してやります。world1は2度目のputsで使っちゃってるので、3度目のputsに渡すことはできないよ、というわけです。

Cleanという言語はこの仕組みを型検査でやってパラレルワールドを防いでいます。

Haskellでは、このworldのようなものをプログラマに直接触らせないようにしています。例えば出力関数putsを、のように「出力を実行した後に、更新後の世界を受け取って実行する関数」を取るように書き換えると:

puts :: String -> World -> (World -> World) -> World

"hello"を2回出力する式はこんなふうに書けます。

puts("hello", world0, λ world1. puts("hello", world1, λ world2. 計算の続き))

λx.式はλ式です。却って見にくくなっちゃったかな。

で、こういうふうに「結果を受け取って次の処理をする関数を渡す」という式はよく出てくるので、

do { puts("hello"); puts("hello"); 計算の続き }

と書いておけば

λ world0. puts("hello", world0, λ world1. puts("hello", world1, λ world2. 計算の続き))

と展開してくれる、という仕組みを作っておくと便利でしょう。この仕組みでは、「世界」が束縛されている変数はプログラマのコードから見えないので、触ることができません。putsなどある仕組みに乗っ取って書かれたコードは間接的に世界に触っていることになりますが、「世界」が何であるかはプログラムから気にする必要はありません。OSも含めたシステム内部ではそれは副作用を含む何かで実現されているかもしれないわけですが、一切見えないのだから無いものと考えても同じことです。

これが「純粋」のしくみです。

ログインすると、残り8件のコメントが見れるよ