Haskell data structure find method

Question

As I'm constructing my data structure I found an issue that I'm having trouble solving it. My data structure "Structure" is String and a list of subStructures.

The issue is in the "lookFor" method below, that is supposed to look for a subStructure named "a" in (Structure b xs) and return it. If not on "b"'s list (xs), it should continue looking in each xs element's list and so on. If not found it should do nothing.

My idea was recursion, and for that, I thought "map lookFor xs" in case it hasn't found the Structure named "a".

Ghci says "Couldn't match expected type Structure with actual type [Structure]" Which I understand, because after all map returns a list of elements and not an element.

data Structure = Structure String [Structure]

name :: Structure -> String
name (Structure a xs) = a

subStrcts :: Structure -> [String]
subStrcts (Structure a []) = []
subStrcts (Structure a xs) = [name x | x <- xs]

lookFor :: String -> Structure -> Structure
lookFor a (Structure b xs) 
    | elem (elemIndex a (subStrcts (Structure b xs))) [0..] = xs !! (fromJust (elemIndex a (subStrcts (Structure b xs))))
    | otherwise = map (lookFor a) xs

Any ideas? Thanks

Furthermore is breadth-first search a requirement, or is any search strategy sufficient? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Nov 22, 2017 at 11:40
Yes, it should be a breadth-first. Can you please elaborate on the Maybe Structure part? I'm new to this language and I'm still in an adaptation period. Sorry and thank you @WillemVanOnsem — Peter Martins
– Peter Martins, Commented Nov 22, 2017 at 11:54
well you do not know if you will find a Structure that matches the query, right? In case you do not find one, you can not simply return null (well Haskell has an undefined, but it is usually better not to use that). In that case you can use a Maybe Structure. A Maybe a, has two possible values Nothing (i.e. the query did not give a result), or Just x with x the result. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Nov 22, 2017 at 11:57
Right, sure it makes sense. However, I'm not aware how can I implement it in lookFor :\ @WillemVanOnsem — Peter Martins
– Peter Martins, Commented Nov 22, 2017 at 12:04

chi · Accepted Answer · 2017-11-22 12:30:02Z

4

A possible solution is:

import Control.Applicative
import Data.Foldable

data Structure = Structure String [Structure]
               deriving Show

lookFor :: String -> Structure -> Maybe Structure
lookFor a s@(Structure b xs)
   | a == b    = Just s
   | otherwise = asum (map (lookFor a) xs)

Above, map (lookFor a) xs searches a in the substructures. This produces a [Maybe Structure], on which we use asum to take the first Just _ value, so that we can return it. (If no such value is found, asum returns Nothing.)

If you don't want to exploit asum from the libraries, defining it is a nice beginner exercise.

answered Nov 22, 2017 at 12:30

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Alberto Centelles · Accepted Answer · 2017-11-22 12:23:23Z

As a recursive structure, you need to set a base case. In your example, this happens when you have exhausted all structures in your list.

As @WillemVanOnsem, it's better to return a Maybe Structure, as it is possible for the lookFor function not to find the Structure

import Data.List (elemIndex)
import Data.Maybe (fromJust, isJust)

data Structure = Structure String [Structure]

name :: Structure -> String
name (Structure a xs) = a

subStrcts :: Structure -> [String]
subStrcts (Structure a []) = []
subStrcts (Structure a xs) = [name x | x <- xs]

lookFor :: String -> Structure -> Maybe Structure
lookFor a (Structure b xs) 
    | null xs = Nothing
    | isJust maybeIndex = fmap (xs !!) maybeIndex
    | otherwise = lookFor a (Structure (name (head xs)) (tail xs))
    where maybeIndex = elemIndex a (subStrcts (Structure b xs))

Collectives™ on Stack Overflow

Haskell data structure find method

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related