結城浩のHaskell日記 RSSフィード

2006-06-12

組み合わせの数 組み合わせの数 - 結城浩のHaskell日記 を含むブックマーク

を見て、とりあえず定義通り(?)作ってみた。

c n k = n^>k `div` k^>k
    where
        n^>k = foldr (*) 1 [n-k+1..n]

関数(^>)は下方階乗冪。冪乗(^)と似ているけれど、だんだん減っていく様子を表現したつもり。

実行結果です。速いなあ。

*Main> 6 `c` 2
15
*Main> 1000 `c` 100
63850511926305130236698511142022274281262900693853331776286816221524376994750901948920974351797699894319420811933446197797592213357065053890

追記:短く書くのが局所的に流行らしい。

ではやってみましょう。

c n k=n^k`div`k^k where n^k=foldr(*)1[n-k+1..n]

47バイト。

追記:id:taninswさんの。

c n k=product[n-k+1..n]`div`product[1..k]

41バイト。

追記:shinichiro.hさんの。

c _ 0=1
c n r=div((n-r+1)*c n(r-1))r

36バイト(改行は1バイトとしてカウント)。

改行はセミコロンでもよいですね(36バイトのまま)。

c _ 0=1;c n r=div((n-r+1)*c n(r-1))r

追記:id:taninswさんの。

c _ 0=1;c n k=c(n-1)(k-1)*n`div`k

33バイト。

関数合成 関数合成 - 結城浩のHaskell日記 を含むブックマーク

ふつけるp.201まで読みました。

関数合成を行う関数は(.)です。f . gだと、gを適用してからfを適用という順序です。

試しに適用順を逆にした関数($$)を作ってみましょう。flip一発ですけれど。

($$) :: (a -> b) -> (b -> c) -> (a -> c)
($$) = flip (.)

f = (1+)
g = (2*)

上のプログラムで、fは「1加える関数」、gは「2倍する関数」です。

f.gも、g $$ fも、「2倍してから1加える関数」になります。

*Main> (f.g) 3
7
*Main> (g$$f) 3
7

関数適用は演算子より優先順位が高いですから、かっこが必要です。f.g 3だと f . (g 3)になってエラーになります。

追記:nobsunから、ご指導がはいりました。

なるほど、確かに>.>や>$>にしたほうが対応がはっきりしますね。しかし >.> や >$> という演算子というのもすごいですね。nobsunのプログラムを読んでいて気づいたこと。

  • 演算子 . もinfixrなんだ。それはそうか。
  • 関数のリストを zipWith ($) [subtract,(*),(+)] [3,2,1] で作れるんだ。それはそうだ。
  • 関数 ($) を「適用」というのは納得。確かにそうだ。

(※結城が山下さんのことをnobsunさんと書かずにnobsunと書くのは、以前山下さんとのメールのやりとりでそういう話が出たからです。別に侮っているわけではありません>誰にともなく)

無名関数とパターンマッチ 無名関数とパターンマッチ - 結城浩のHaskell日記 を含むブックマーク

ふつけるp.197まで読みました。

無名関数(anonymous function)の引数のところでもパターンマッチができます。

以下の関数fは、(x:xs)というパターンマッチで引数が束縛されます。

f = \ (x:xs) -> [x] ++ "-" ++ xs

実行結果です。

*Main> f "Email"
"E-mail"

日付間違い 日付間違い - 結城浩のHaskell日記 を含むブックマーク

日記の日付を間違っていました。トラックバック・コメントが一部消えちゃってごめんなさい。

変数it 変数it - 結城浩のHaskell日記 を含むブックマーク

GHCiでは、変数itは、最後に評価した値で束縛されるようです。

taninswさんの日記を見ていて知りました。

Prelude> let x = 123
Prelude> x
123
Prelude> it
123
Prelude> let y = 456
Prelude> it
123
Prelude> x + y
579
Prelude> it
579
Prelude> y
456
Prelude> it
456
Prelude> it + it
912
Prelude> it
912

追記:nobsunからトラックバック。

わたしもやってみよう。

__   __ __  __  ____   ___      _________________________________________
||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__||  __||     Copyright (c) 1994-2003
||---||         ___||           World Wide Web: http://haskell.org/hugs
||   ||                         Report bugs to: hugs-bugs@haskell.org
||   || Version: Nov 2003       _________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions

Type :? for help
Prelude> 123
123
(24 reductions, 62 cells)
Prelude> $$
ERROR - Syntax error in expression (unexpected symbol "$$")
Prelude> it
ERROR - Undefined variable "it"
Prelude> :set -r$$
Prelude> $$
ERROR - Undefined variable "it"
Prelude> 123
123
(22 reductions, 34 cells)
Prelude> $$
123
(22 reductions, 34 cells)
Prelude>

あれ? $$ が使えない。バージョンのせいかな?

追記::set -r$$ するまでは使えていないみたいです。ともあれ、Hugsはバージョンアップしようと思いますが。

追記:↑の追記は私の勘違いだったようです。2003のバージョンでも$$は使えました。Hugsはバージョンアップしましたが。

パターン束縛 パターン束縛 - 結城浩のHaskell日記 を含むブックマーク

ふつけるp.189まで読みました。

変数を束縛するのにパターンを使うことができます。以下の例では、パターンを使って変数xとxsを束縛しています。

a = [x] ++ "-" ++ xs
    where
        (x:xs) = "Email"

実行結果です。

*Main> a
"E-mail"

nobsunnobsun2006/06/12 08:38わたしのHugsのバージョンは
Hugs> :v
-- Hugs Version May 2006
です。
プロンプトから :set コマンドを引数なしで与えると現在の設定がでると思います。-r文字列 の文字列部分が ghci の it にあたるものです。

..2006/06/12 22:38> length "c n k=n^k`div`k^k;n^k=product[n-k+1..n]"
39

hyukihyuki2006/06/12 23:08すごい!…と思ったんですけれど、GHCだと
Ambiguous occurrence `^'
というエラーが。

shinichiro_hshinichiro_h2006/06/12 23:142行ですが一応36byteやってました。http://shinh.skr.jp/m/?date=20060607#p01

6/6の「.」6/6の「.」2006/06/13 00:53念のため: 「.」さんは一般名詞で6/6の「.」と6/12の「.」さんは別の人です。私も「productがありますよ」と書こうとしてました。

hyukihyuki2006/06/13 01:05ということは、「.」さんというよりも、「_」さんだったのですね(^_^)

taninswtaninsw2006/06/13 02:5733byteになりました(´ー`) http://d.hatena.ne.jp/taninsw/20060612#1150134397