[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part16 (978ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
766: 2011/12/20(火)16:29 AAS
742がやってることはホームレスを無差別にいじめてる事と同じでしょ。
767(6): 2011/12/20(火)21:54 AAS
listAは重複がないリストとする。
listBは空でなく、順序は不明だがlistAの要素の連続になっている。
listAの要素であるxを渡された時、それがlistBと比較して前方にあるか
後方にあるか、それともlistBに含まれるかを判定したい。
例で書くと
listA = ["A","B","C","D","E",...]
listB = ["C","D","B"]
xが"E"なら、listBに含まれるB,C,Dに対して「後方」ということになる。
このとき、haskellらしい考え方だとどういうアプローチになる？
俺の手続き脳だと
1. xがlistBにあるかどうかを判別
2. xとlistBそれぞれの要素のlistA内での位置を調べる
3. 調べた位置を比較して「前方」「後方」を判定する
と考えたんだけど、ザ・手続きっぽくてダサいよなぁ、と思って。
768: 2011/12/20(火)22:49 AAS
こんな感じ？
filter (flip all listB . (/=)) listA
769: 2011/12/20(火)22:52 AAS
ごめん問題読んでなかった。取り除くんじゃないのな。
770(1): 2011/12/20(火)22:55 AAS
>>767
めっさ力技
data Pos = F | M | E deriving Show
getPos :: Eq a => [a] -> [a] -> a -> (Maybe Pos)
getPos listA listB = fmap f . (`lookup`listE) where
listC = map (`elem` listB) listA
listE = zip listA $ zip listC $ scanl1 (||) listC
f (True,_) = M
f (False,False) = F
f (False,True) = E
listA = [0,1,2,3,4]
listB = [2,3,1]
x=0
main = do
let g = getPos listA listB
print $ g 0
print $ g 1
print $ g 2
print $ g 3
print $ g 4
771(4): 2011/12/20(火)23:35 AAS
>>767
1. listAをlistA1 ++ [x] ++ listA2にわける
2. listA1とlistBのintersectionを取って判定
f listA listB x =
if y == 0 then 1 else if y == length listB then -1 else 0
where y = length $ takeWhile (/= x) listA `intersect` listB
772(1): 2011/12/21(水)01:20 AAS
>>767
f listA listB x = (elem x as, elem x listB) where as = takeWhile (not.flip elem listB) listA
773: 2011/12/21(水)08:25 AAS
>>771
(y == 0)のあとに(elem x listB)でもう一回場合分けが必要でない？
774: 2011/12/21(水)12:32 AAS
>>759
元々４月の予定だったよな……
775(1): 2011/12/21(水)12:43 AAS
>>767 の解法としていくつか提示された例は、
たとえば1ヶ月後とかに自分が読んでも、あるいは他人が読んでも、
どんな計算をして答えを求めているのか簡単に分かるもんなの？
776(2): 2011/12/21(水)16:52 AAS
listBの要素はソートすればlistAの連続部分列になるってこと？
777: 2011/12/21(水)17:20 AAS
>>776 listAは整列だという仮定はない。「listAでの出現位置」に基づいてソートするなら話は別だが。
778(6): 2011/12/21(水)19:40 AAS
>>767
data Where = Before | Here | After
whereIncluded :: (Eq a) => [a] -> [a] -> a -> Where
whereIncluded _ [] _ = After
whereIncluded (a:as) (b:bs) x
| x == b = Here
| x == a = if elem x bs then Here else Before
| otherwise = whereIncluded as bs x
[説明]
・listA と listB それぞれの head と x を比較する
・listB の head と x が同じなら、x は listB に含まれる
・そうではなく listA の head と x が同じ場合、
x が listB に含まれていなければ、x は後方にある
・どちらの head とも異なっていれば、両者の tail に対して同計算を繰り返す
・計算を繰り返した結果 listB の tail が空なら、x は後方にある
提示された条件を全て完全に満たすものとして式を書いたので、
エラー処理は省いてある
779: 767 2011/12/21(水)21:02 AAS
>>770,771,772,778
まさかこんなに素早く返事があるとは思ってなくて
反応遅れました。すみません。
具体的なコード例までわざわざありがとうございます。
見事に誰一人としてelemIndexなんて使ってないですね……。
順序を調べる、という発想自体を捨てないと駄目だということが
よくわかりました。
>>775
個人的には770さんの例以外は見て何をしているかは
すぐ把握できました。
>>776
777さんが返してくれていますが、listAは整列とは限らないです。
listAの位置に基づいてlistBをソートすれば、listBは確かに連続
部分列になります。
というわけで、どうも皆さんありがとうございました。
780(3): 2011/12/22(木)05:28 AAS
>>778
whereIncluded [1..6] [5] 4 = whereIncluded [2..6] [] 4 = After
781: 2011/12/22(木)07:22 AAS
>>780
あぁなるほど、そうか
ちょっと修正案を考えてみる
782: 778 2011/12/22(木)07:52 AAS
>>780 に指摘されて修正案を考えてる時に、
全然違うアイデアが思い浮かんだんだが、
これは今まで出てきたかな（特に >>771 と同類か）
listA から x の位置を探す
x の位置の直後から
783(2): 778 2011/12/22(木)07:55 AAS
途中でレスってしまった
>>780 に指摘されて修正案を考えてる時に、
全然違うアイデアが思い浮かんだんだが、
これは今まで出てきたかな（特に >>771 と同類か）
listA から x の位置を探す
x の位置の直後から listB の要素数分の要素をリストとして取り出す listC
x が listB に無い場合、head listB が listC に有れば「前」
head listB が listC に無ければ「後ろ」
784(1): 778 2011/12/22(木)08:55 AAS
>>783
訂正
> x の位置の直後から listB の要素数分の要素をリストとして取り出す listC
x の位置の直後から末端までをリストとして取り出す listC
785: 778 2011/12/22(木)12:54 AAS
>>783,784
式にするとこんな感じ
whereIncluded :: (Eq a) => [a] -> [a] -> a -> Where
whereIncluded as bs@(b:_) x
| elem x bs = Here
| elem b as' = After
| otherwise = Before
where as' = takeWhile (/=x) as
ダサいかな
786: 2011/12/22(木)20:08 AAS
Haskell Platform じゃなくて素の GHC の方には、
random パッケージってデフォルトでは入ってないんだね
地味に驚いた
787: 2011/12/22(木)21:36 AA×
外部ﾘﾝｸ:www.haskell.org
788: 2011/12/22(木)21:56 AAS
遅延I/O怖い＞＜
789: 2011/12/22(木)22:55 AAS
モナドって大した概念なの？
790(2): 2011/12/22(木)22:59 AAS
ものごとを抽象化するための仕組みとしては大したもんだよ
791(1): 2011/12/23(金)10:28 AAS
>>790
なんかいい例希望
モナドはものごと全部を抽象化するんじゃないよね？
792: 2011/12/23(金)10:30 AAS
STMとか？
793: 2011/12/23(金)12:02 AAS
>>790 >>791
そうだな。なんでも抽象化できるんならこれまた意味不明になるし。
だいたい、何なんだよ抽象化って。
794: 2011/12/23(金)17:44 AAS
モナドによる抽象化ってのは、だいたい(Monad m) =>で始まる型のある関数を書くこと
具体例はControl.Monadとか見れば
795(1): 2011/12/23(金)17:52 AAS
それで、何をどう抽象できて、何は抽象できないの？
モナドで抽象する前と後とで何が変わるの？
上下前次1-新書関写板覧索設栞歴
あと 183 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.031s