Anonymous user
Nested templated data: Difference between revisions
→{{header|Haskell}}: added solution
Alpha bravo (talk | contribs) (Added AutoHotkey) |
(→{{header|Haskell}}: added solution) |
||
Line 360:
The unused payloads have indices of : [0 6]
</pre>
=={{header|Haskell}}==
The problem is ideal for demonstration of the Functor and Traversable concepts in functional programming.
Being a ''functor'' allows changing the contents of a complex data structure, keeping structure unchanged (via <tt>fmap</tt> function). This property already matches the template idea, but we can go further. The structure may be ''foldable'' as well, allowing aggregation of contents, using arbitrary monoid or aggregating function. Moreover foldable functor may be ''traversable'', giving the ability to modify the complex structure contents with computations held in a given applicative or monadic context.
All these properties are well defined, have solid theoretical background and are presented by classes: <tt>Functor</tt>, <tt>Foldable</tt> and <tt>Traversable</tt>.
For wide class of data structures instances of all these classes may be derived by the compiler in a sound unique way. The data template given in the task is exactly the case of a functor.
If we do not bother about neat textual representation, the definition of traversable nested template is as easy as following:
<lang haskell>{-# language DeriveTraversable #-}
data Template a = Val a | List [Template a]
deriving ( Show
, Functor
, Foldable
, Traversable )</lang>
Functorial property of a data type is sufficient for defining the universal substitutor of keys/indices by payload data:
<lang haskell>subst :: (Functor t, Eq i) => [(i,a)] -> t i -> t (Maybe a)
subst d = fmap (`lookup` d)</lang>
It is possible to turn any list of payloads into a map by simple helper function:
<lang haskell>indexed :: [a] -> [(Int, a)]
indexed = zip [0..]</lang>
Now we can make substitutions to flat lists or nested templates:
<lang haskell>t :: Template Int
t = List [ List [Val 1, Val 2]
, List [Val 3, Val 4, Val 10]
, Val 5]
payloads :: [(Int, String)]
payloads = [(i, "payload#"++show i) | i <- [0..6]]</lang>
<pre>λ> subst payloads [6,2,1,2]
[Just "payload#6",Just "payload#2",Just "payload#1",Just "payload#2"]
λ> sequence $ subst payloads [6,2,1,2]
Just ["payload#6","payload#2","payload#1","payload#2"]
λ> indexed "traverse"
[(0,'t'),(1,'r'),(2,'a'),(3,'v'),(4,'e'),(5,'r'),(6,'s'),(7,'e')]
λ> subst (indexed "traverse") [6,7,1,3,4,1]
[Just 's',Just 'e',Just 'r',Just 'v',Just 'e',Just 'r']
λ> sequence . subst (indexed "traverse") [6,7,1,3,4,1]
Just "server"
λ> subst payloads t
List [ List [Val (Just "payload#1"),Val (Just "payload#2")]
, List [Val (Just "payload#3"),Val (Just "payload#4"),Val Nothing]
, Val (Just "payload#5")]
λ> sequence $ subst payloads t
Nothing</pre>
In the last case not all substitutions could be done, so the whole substitution failed. The <tt>sequence</tt> function works for any traversable structures.
Foldable properties of templates (with a little help of monoids) allow to implement extended tasks.
<lang haskell>unusedIndices :: (Foldable t, Eq i) => [(i,a)] -> t i -> [i]
unusedIndices d = foldMap unused
where unused i = maybe (pure i) (pure []) $ lookup i d
unusedData :: (Foldable t, Eq i) => [(i, a)] -> t i -> [(i,a)]
unusedData = foldr delete
where delete i = filter ((i /= ) . fst) </lang>
<pre>λ> unusedIndices payloads t
[10]
λ> unusedData payloads t
[(0,"payload#0"),(6,"payload#6")]</pre>
=={{header|J}}==
| |||