Firstly, Thanks! I take from the both replies, to first create data-structures for rows, columns and diagonals. That approach makes sense to me. On 03/23/2012 01:21 AM, Ozgur Akgun wrote:
Hi,
import Data.List import qualified Data.Set as S
rows :: Ord a => [[a]] -> S.Set [a] rows = S.fromList
cols :: Ord a => [[a]] -> S.Set [a] cols = S.fromList . transpose
diagonals :: Ord a => [[a]] -> S.Set [a] diagonals [] = S.empty diagonals xss = S.union ( S.fromList $ transpose (zipWith drop [0..] xss) ) ( diagonals (map init (tail xss)) )
allWords :: Ord a => [[a]] -> S.Set [a] allWords xss = S.unions [ rows xss , cols xss , diagonals xss , diagonals (map reverse xss) ]
... search :: Ord a => [a] -> [[a]] -> Bool search word xss = not $ null [ () | xs <- S.toList (allWords xss), word `isPrefixOf` xs ]
If I understand correctly, in this solution it is assumed that that a word must be a complete line (row column or diagonal), correct? I was not clear in original mail, the word can also be in the middle of line, but it seems easy enough to adjust the sample for this. I do not understand why a set is used. Couldn't just a list be used here, or is there some performance advantage I do not see? I find it very difficult to estimate the performance of an haskell program. The other solution of Lorenzo Bolla utilizes Data.Vector. Does that give a performance advantage in this case? Thanks! Nathan