[Haskell-beginners] Searching for word in 2D array

[Lorenzo Bolla]

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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120323/f6afd03e/attachment-0001.htm>