Tuesday, June 26, 2007

Search in Haskell

I've been playing around today with search in Haskell, and besides from some overly technical papers and a confusing explanation on the YAHT wiki book, I haven't found anything useful. So I though I'd put up what I could figure out.

First, let's use type classes to get some modularity. Search can be over trees or graphs or whatever, basically we just need states and a function to give us the children of a node. We also are going need to compare states to check if we have reached the goal.

> class (Ord a) => SearchState a where
> children :: a -> [a]

For instance, let's say we are trying to solve the numeric maze given in the haskell wiki. In this problem our state is just an integer.

> newtype NumMaze = NumMaze Integer deriving (Show, Eq, Ord)

And here is the instantiation. Our operations to generate children are (x+2), (x*2), (x/2). So

> instance SearchState NumMaze where
> children (NumMaze n) =
> map NumMaze $
> [n+2, n*2]++[n `div` 2 | 2 `divides` n]
> where divides a b = b `mod` a == 0

Now we can write very generic functions for the search operations. We'll start with a monadic depth first search. Depth first search is very natural for functional programming (if we don't worry about blowing the stack). We dive in with recursion. There is good explanation of this on the haskell wikibook here. Instead of using a graph, we use our search state and simplify the code by using a fold.

> dfs :: (SearchState a,MonadPlus m) => a -> a -> m[a]
> dfs start target
> | start == target = return [start]
> | otherwise =
> foldr mplus mzero $
> [ dfs c target >>= \path -> return (start:path)) |
> c <- children start] The code has two cases. If we have reached the goal, it returns a list of success with the result. Otherwise, in the list comprehension it tries searching each child. If it finds a successful path, it adds it returns it. You might wonder where we handle failure. If there are no children, the fold returns mzero which will propagate failure to its parents. When the parent gets a failure, mplus will try a different path, and we have backtracking. Next we'll try breadth first search. Here is one way to do it by passing a queue as an accumulator. > bfs :: (SearchState a,Monad m) => a -> a -> m [a]
> bfs start target = bfs' [[start]] >>= return . reverse
> where
> bfs' [] = fail "No Path"
> bfs' ((s:r):ns)
> | s == target = return (s:r)
> | otherwise = bfs' (ns ++[c:s:r |c<-children s]) We can make this faster by adding a set to keep track of states that we have already visited. > import Data.Set (empty, notMember, union, fromList)

> bfs2 :: (SearchState a,Monad m) => a -> a -> m [a]
> bfs2 start target = bfs' [[start]] empty >>= return .reverse
> where
> bfs' [] _ = fail "No Path"
> bfs' ((s:r):ns) seen
> | s == target = return (s:r)
> | otherwise = bfs' (ns ++new') seen'
> where
> new' = [c:s:r|
> c <- children s, > c `notMember` seen]
> seen' = seen `union` (fromList $ map head new')

So these functions are nice, and they are how I would write them in O'Caml. But they just feel too ugly for haskell. I know, I'm getting spoiled. So I thought I would give a shot at a lazier version. The rest of this entry is my very basic understanding of the Functional Pearl Breadth-First Combinators.

First, depth first search. I visualize it like this. Imagine, that the states form a tree, and we want to first transform the tree to a stream, and then process it linearly. Haskell makes this absurdly easy. First, imagine that we can linearize all the children searches. This gives us a matrix-like list of streams (since we are doing DFS, we hope they are not infinite, but that does not break the formulation) i.e.

[[Child1, Child1.1, Child1.2 ...],
[Child2, Child2.1, ...],
...
]

Since this is DFS, we want to explore these in order. This means all we need to do in concat them, and we have the full traversal. Bam!

> lazyDFT :: (SearchState a) => a -> [a]
> lazyDFT start = start : (concat $ map lazyDFT $ children start)

In the paper they call this the "and" operator for logical combination.

Now, what about Breadth-first search. Well we want to move one level at a time instead of following a single path to its end. If we know that our tree is balanced, we can simply transpose the matrix and then take the concat

[[Child1, Child1.1, Child1.2 ...],
[Child2, Child2.1, ...],
...
]
-->
[[Child1, Child2, Child3 ...],
[Child1.1, Child2.1, ...],
...
]

Here is the code using Data.List's lazy transpose function.

> lazyBFTBal :: (SearchState a) => a -> [a]
> lazyBFTBal start =
> start:(concat $ transpose $ map lazyBFTBal $ children start)

Hmm... Not sure the best way to proceed here. In all honesty, I find the rest of the combinators paper to be a bit confusing to say the least, but I'll try to fake it. I want to make sure I traverse the tree in order, so I'll preserve the order at each level. The new type signature is .

lazyBFT :: (SearchState a) => a -> [[a]]

and the matrix looks like,

[[[Child1], [Child1.1, Child1.2] ...],
[[Child2], [Child2.1], [Child2.1.1]],
...
]
transposed to
[[[Child1], [Child2] ...],
[[Child1.1, Child1.2], [Child2.1],...],
[ [Child2.1.1],..]
...
]

and then we concat each row,

[[Child1,Child2,...], [Child1.1,Child1.2],[Child2.1.1]]

Score! Back to where we started.

The code looks like,

> lazyBFT start = [start]:(map concat $ transpose $ map lazyBFT $ children start)

If I use it on the problem we started with yields.

*Main> take 3 $ lazyBFT (NumMaze 10)
[[NumMaze 10],[NumMaze 12,NumMaze 5,NumMaze 20],[NumMaze 14,NumMaze 6,NumMaze 24,NumMaze 7,NumMaze 10,NumMaze 22,NumMaze 10,NumMaze 40]]

Now lets add some of the pruning back.

> lazyBFT2 seen start = [start]:(map concat $ transpose $ map (lazyBFT2 seen') $ c)
> where c = [c| c <- children start , c `notMember` seen] > seen' = seen `union` (fromList c)

*Main> take 3 $ lazyBFT2 (singleton $ NumMaze 10) (NumMaze 10)
[[NumMaze 10],[NumMaze 12,NumMaze 5,NumMaze 20],[NumMaze 14,NumMaze 6,NumMaze 24,NumMaze 7,NumMaze 22,NumMaze 40]]



Okay, I'll stop here for now. Pretty cool stuff. I wonder, is there is a lazy way to do this pruning? Maybe next post...

39 comments:

ArdellaJ said...

a片洪爺色情網a色情小說a色情影片av色情a片下載av色情dvdav免費色情片av免費色情影片av女優線上免費色情影片av女優色情影片av成人情色色情光碟圖庫有碼女優色情影片色情av女優介紹go2avaa色情免費看aa色情網站85論壇色情18禁色情網站18禁色情小說18禁地色情線上遊戲18禁地色情遊戲18禁地少女色情遊戲18禁成人色情漫畫18色情排行榜18街色情18歲色情影片3d色情3d色情遊戲520色情影片69色情網85cc成人色情片觀看85色情街85街色情av直播室情色小說72免費情色影片777-情色光碟網777情色光碟網7kiss情色網85cc免費影片-成人-情色論壇-成人文章

才董 said...

格主的部落格內容真豐富~~看得很開心..................................................

ya said...

來看看你囉~blog很棒! ........................................

茂一 said...

成人色情電影院線上免費色情短片色情動畫影成人色情動畫色情介紹台灣好色一葉晴視訊力小遊戲力的小遊戲力的色小遊戲力的色遊戲力的遊戲十八成人網站十八歲成人十八歲成人論壇十八禁小遊戲十八禁小說三級片線上觀看下載日本電影下載免費看日本av女優電影八五街八大成人圖庫人做愛姿勢一葉貼圖區一葉貼影片一葉貼影片區一葉影色站一葉擎一碼丁子褲淫蕩學生妹ut美女聊天室成人遊戲情色a片

林淑凡 said...

要保持更新呦,加油!!!期待你的新文章!!! .........................................

宗弘 said...

how do u do?xvideo打飛機專用網洪爺免費洪爺色情片洪爺貼圖區洪爺成人線上洪爺影城洪爺色論壇洪爺貼圖洪爺成年人網洪爺免費色情洪爺色情貼援交妹辣妹野球拳情色文學情趣聊天室性感辣妹裸體遊戲做愛偷拍一夜情視訊洪爺色情貼洪爺免費色情洪爺成年人網洪爺貼圖洪爺色論壇洪爺影城洪爺成人線上洪爺貼圖區洪爺色情片洪爺免費洪爺色情貼洪爺免費色情洪爺成年人網洪爺貼圖洪爺色論壇洪爺影城洪爺成人線上洪爺貼圖區洪爺色情片洪爺免費洪爺免費洪爺色情片洪爺貼圖區洪爺影城洪爺色論壇洪爺貼圖洪爺成年人網洪爺免費色情洪爺色情貼洪爺成人線上

RafaelLetso21555 said...

人必須心懷希望,才會活的快樂,日子才過得充實,有意義,有朝氣,有信心。........................................

虹玟 said...

憂能傷身,保重哦!........................................

SungR_Auclair0佳亦 said...

謝謝您的分享~感恩唷!!..................................................

品華yur1095is_newson1 said...

路過--你好嗎..很棒的BLOG.........................................

韋于倫成 said...

很以有啟發性的故事阿~感謝大大分享^^........................................

韋于倫成 said...

幸福不是一切,人還有責任。 ..................................................

嘉慧 said...

黑色豪門企業綜合娛樂論壇 ez洪爺的家 嘟嘟情人色網dvd hot辣妺視訊網 限制性漫畫 一夜情人視訊 av1688大天使娛樂網 bt成人網 go2av成人聊天室 免費a長片線上看,女優影片 無碼 av影片 美眉 美女 聊天室 遊戲區 18成人http 17hi tw 情色聊天 百分百貼圖區亞洲avdvd 免費視訊聊天mm17i 情色a片 88天下淫書,少年阿賓系列小說,中文情色文學小說 0401線上影城 視訊做愛 杜蕾斯成人 亞洲辣妹妹影音視訊聊天室 美女聊天室 麗的情色小遊戲 韓劇人妻的秘密85cc影城 playboy國際中文網 免費影音視訊hibb 6k情人網暗戀視訊 免費視訊4h 無碼av女優微風成人區 甜心寶貝直播貼片aio交友愛情館 xvediox免費影片 視訊交友520show net 視訊美女聊天 kk 台灣kiss911h影片線上a片 aaaa 片俱樂部 2girl女子拉拉學園 av168成人網 辣妹影片直播台南援交友留言 omyga美色女影城 go2av免費影片情色 網站 ut聊天室kww 情人視訊高雄網 性行為補給站 後宮視訊聊天網 網愛mmshow 主播情人視訊情色交友 104愛戀速配網 視訊美女聊天室 免費色咪咪影片網 兼職援交 影音視訊聊天室dudu sex

韋成 said...

A stitch in time saves nine...................................................

ShilaLong嘉雯 said...

Well done!............................................................

BryannaR22369 said...

男女互悅,未必廝守終生,相愛就是美的。..................................................

萱祥 said...

原來天鵝嫁給癩蛤蟆就會生出醜小鴨.................................................................

王邦鈺 said...

Pen and ink is wits plough. .................................................................                           

韻玉 said...

死亡是悲哀的,但活得不快樂更悲哀。....................................................................

貴寶 said...

當一個人內心能容納兩樣相互衝突的東西,這個人便開始變得有價值了。............................................................

群平群平 said...

認清問題就等於已經解決了一半的問題。.................................................................

張怡 said...

如果相遇.你會感到相知.那麼.有一種習慣叫做陪伴;如果陪伴.你會感到珍惜.那麼.有一種甜蜜叫做存在!..................................................................

芸茂芸茂 said...

A friend in need is a friend indeed...................................................................

曹依潔曹依潔 said...

文章是心情的反應~~祝妳天天寫的都是讓人開心的好文章哦!!............................................................

國昆 said...

到處盡心,即為快事;舉步踏實,便是坦途。......................................................

楊儀卉 said...

人生就像一顆核桃,必須敲破它,才會顯出他的內容。......................................................

婷珊 said...

臨淵羨魚,不如退而結網。......................................................

香昱信張君林 said...

來向你問安喲!!!..................................................................

楊儀卉 said...

初次拜訪,踩踩您的格子,跟您拜個碼頭囉~~..................................................................

紹函紹函 said...

文章不求沽名釣譽,率性就是真的..................................................................

李威昌v彥霖 said...

每天都是新的心情~~希望都是好心情!!!!..................................................................

劉隆季劉隆季 said...

做好事,不需要給人知道,雖然只是一件微不足道的事,但我相信,這會帶給我快樂。..................................................

謝翁穎翰毓珍 said...

Make yourself necessary to someone..................................................................

建邱勳 said...

當我微笑時,世界和我一起微笑;當我快樂時,世界和我一起活躍。..................................................

文王廷 said...

幸福不是一切,人還有責任。............................................................

偉曹琬 said...

生命是一頓豐富的宴席,有人卻寧可挨餓................................................

琬群學葉安高 said...

看到你的更新是一種幸福!..................................................................

惠奇 said...

善言能贏得聽眾,善聽才能贏得朋友。......................................................................

佳張張張張燕張張張張張 said...

這不過是滑一跤,並不是死掉而爬不起來了。..................................................