I'm not sure Data.Set would work, because afaik, Sets don't preserve ordering: so a row like "abc" and "cab" would be represented by the same Set.

Data.Vector is more efficient, but I like it more than List when I have to do slicing.

hth,
L.



On Fri, Mar 23, 2012 at 10:01 AM, Nathan Hüsken <nathan.huesken@posteo.de> wrote:
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

_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners