Reinforcement Learning: Actor Critic

Why Reinforcement Learning?

Reinforcement learning is typically used to generate a sequence of actions to achieve a goal. Note that it is different from the classification problem, which answers a question like whether a given feature vector should have a yes/no (or categorical) answer. However, each step of the sequence of actions may be decided similar to a classification problems: given a feature vector for the current environment state, what is the next action to generate in the sequence to achieve a goal state. Main differences:

• a sequence of actions (trajectory) vs. a single decision
• environment may be a black box.

The goal state is assigned with a reward to guide the action. There are 2 approaches to solve it: find a policy function that given a state S, returns the probability to pick an action a. Or, find a value function that predict the reward in this state - use this value function to greedily pick an next action a that gives the most award (the observed reward at the next state S + the guessed reward moving from S).

Note that with a policy function, the actions are picked randomly by their probability. The policy function could be used to randomly sample a few trajectories to test out the rewards, and take an average to represent how good a state is. In reality there could be many trajectories. We just need a few sample to have a Monte Carlo estimation.

Describe RL in a more human-understandable fashion

It is a maze game, you are asked to find a path from point A to point B.

But you don't know how the maze looks like. However, putting a BBQ chicken at point B, you can follow the smell from point A to reach point B. The BBQ chicken here is the reward, and the smell is the expected future reward (call it return).

But the smell isn't there, either. To implement the smell, we need to assign every step toward the food a greater imagined smell value. This is the discounted return.

But we don't know where the food is, either. So we take random actions until reaching the BBQ, and then assign our steps with imagined smell values.

If we step on poop during the random exploration, assign our steps with negative smell values, so that they are visited less often. And try walking again following the imagined smell.

How to assign an imagined smell value to a step? Use a neural network, or any model.

Applications:

• Chatbot - outputs a sequence of words, to provide answer to a question
• AlphaGo - chess, use a sequence of moves to value best state
• Control - plan a trajectory to control robot / game to reach a certain state.

Q Function

Q function is the quality of an action in an state S. It is usually guessed from a observed trajectory - by the sum of the observed rewards from an intermediate step i to the end state. This sum also have a named called discounted return. (It is called discounted because the sum is a weighted sum - a reward at a further step has less weight in the sum)

Actor Critic

In Actor Critic, two networks are trained. Critic network gives a score of how well an action is under an environment state. (So it takes 2 variables: action and state) Critic network is trained based on reward from the system. Actor network chooses a sequence of actions under each environment state so that the average score from the Critic network is higher. (So it takes 1 variable: state) It is trained based on the scores from the Critic network.

Proximal Policy Optimization

PPO is an improvement based on Actor Critic, where the learning on actor is capped to avoid taking too large of a step. It can be done by 2 ways: limit the loss - it is too large, clip to the max allowed value; Or, use a ratio between the probability of an action in the new policy and the old policy.

Trust Region Policy Optimization

In Trust Region policy optimization, use a function L to approximate a target function which we want to find parameters for. L and the target function are only similar within a small range. In this range, find the parameters for the max value of L, assuming it has the same parameter of the target function. Then start over from finding the the approximate function L again. The process repeats between Approximation and Maximization.

The Monte Carlo method can be used to make the approximation L, by taking sample trajectories.

To make sure the new parameters after maximization are within a small region to the old parameters, KL divergence is used to compare the probability distribution of the policy function. Or it is also possible to measure the distance of the parameters directly.

Study Note: Stochastic Gradient Descent, Dueling network, Neural Architecture Search

Mini-batch Stochastic Gradient Descent:

• Stochastic Gradient Descent with pytorch:
• keep the gradient in general (with  parameter momentum > 0)
• work with large data by choosing a mini-batch - using DataLoader to randomly choose datapoints to update.
• Pytorch SGD doesn't really do the stochastic part, despite of the naming
• Sample on datapoints with a higher loss at a higher probability.
• Give sample datapoints of a higher loss of a large learning rate, and give datapoints of a smaller loss at a smaller learning rate, as suggested in this RL: Experience Replay video (in Chinese).

Dueling network:

• Write the Q* function to be the sum of two neural networks:
• Q(s, a) = V(s) + A(s,a) - max A(s,a)
• Note that since Q depends on the sum of two neural networks,  under the same Q value, the two Neural networks could be unstable by shifting the center from network output 1 and adding the shifted portion to the network output 2.  Fortunately, the max A(s,a) term prevents this from happening, as changing shifting value would the  max A(s,a) term to change, resulted as varying Q. The max A(s,a) term in practice can be replaced with mean A(s,a) for better performance.

  

Neural Architecture Search

• You have laid out a set of neural network layers for the same purpose, or maybe the esame neural network layer but with different choices of number of parameter - should I use 20 neurons or 30 neurons? or should ResNet works better one part of the layer than just FullyConnected? etc. The goal of the neural architecture search is to find out a better configuration.
• Naive approach: give every configuration a try. If there are 3 candidates neural network layer, train on every one configuration. This becomes out of hand quickly when there are layers connected in series - the numbers of choices are multiplied.
• Differentiable Neural Architecture Search:
• Construct a super net by connecting all candidate layers that you want to try in 1 single network in parallel, and sum the results from each layer by a weighted sum using a Softmax layer. The weights are learnable parameters. Then train the super net. All layers will be trained, and their importance will be listed in the learned weight. The one with the largest weight is the winner. Keep that layer and throw away those layers with smaller weights.
• It was explained in this video (Chinese). It is also possible to add running time to the  weight so that the choice from this process considers both accuracy and performance.

 

Study note: Bipartite Graph

14-1Bipartite Graphs 

• Bipartite graph is one with two sets of nodes. Edges can exist between the sets, but not among a set.
• Algorithm to identify if a Graph is Bipartite: given 2 colors, traverse nodes color them color them and color the neighbor nodes with different colors. If a node has a conflicted color with earlier color decision, the graph is not a Bipartite graph.

14-2 Bipartite Graph Matching

• Define Matching: pairing nodes from two sets in a Bipartite graph, without using repeating elements. (two nodes cannot share the same partner node)
• Max-cardinality Bipartite Matching - include as many pairs as possible.
• Greedy algorithm: iterate through nodes in one side, and find one partner node. (Skip the node if no partner can be found)
• Convert Matching problem into Network Flow
• By connecting a source node to 1 set and connecting a sink to the other set. Then find network that could flow through from source to sink
• assign each edge with 1 weight.
• Solve the network flow problem by Ford-Fulkerson algorithm, and the result paths gave the optimized matching.

14-3 Maximum-Weight Bipartite Matching

• Let edges between 2 sets of nodes to be a matrix. Each edge has a weight. The goal is to find the matching with the max total weights.
• Hungarian Algorithm can solve this by finding the minimum weight.
• prerequisite: the cardinality of  of the two sets must be the same. That means the number of nodes must be the same.
• Time complexity: O(n**3)
• Negating the weights converts the algorithm from finding the minimum total weight to maximum total weight.

Write to DeltaTable using Python WITHOUT pandas (using pyarrow)

 I am trying to write data in DeltaTable format from an AWS Lambda Function, but AWS Lambda Function limits to 250MB. The deltalake library takes 247MB, which exceeds the limit along with pandas. Since the deltalake library included pyarrow, I need to find a way to write a data frame without including pandas.

Here is how:

Quick Tutorial: Kalman Filter

I assume you already heard of Kalman Filter. In general, you are controlling a moving vehicle and would like to know where it is at the next moment.

You made your guess of the vehicle's next moment based on your current speed, and at the next moment you also measured the vehicle's next location. Neither of them were accurate. Thus, both of them were in Normal distributions, with some room for errors / noise. The best estimation is to take a product of the two Normal distributions.

Here is how to take the product of two Normal distributions, based on this video (voiced in Chinese):

 Taking a product of two Gaussian Distribution X ~ ( µ1, δ1) , Y, ~ ( µ2, δ2), the result Gaussian Distribution is:

   k = δ1 / (δ1 + δ2)

    µ = µ1 + k * ( µ2 - µ1 )

   δ ** 2 =  δ1** 2 + k * δ2 ** 2

How do I guess my next location? Use middle school math: knowing the current location p and speed v, we could guess the location of the vehicle in the next moment to be: 

pk = pk-1 + vk-1 * t

vk = vk-1

(Since there is no external force, the next speed u is constant.)

Let state X = (p, v) be the current position and speed of the vehicle, rewrite the two formulas into a matrix form. That is:

pk = 1* pk-1 + t * vk-1

vk = 0* pk-1  + 1 * vk-1  

Then write (pk, vk) as Xk and ((pk-1, vk-1) as Xk-1 and rewrite the expressions above as matrix multiplication

Xk =  [1 , t ]  * Xk-1

          [0, 1]

Call the matrix as F in front of Xk-1 . The formula becomes Xk =  F * Xk-1 . We will use the matrix F later.

If there is an external acceleration a, then next p needs to add a * t**2 / 2. and next u needs to add a * t, middle school math again. See this part of the video . The external acceleration is your control. It is how much force to apply to make the vehicle faster.

Xk =  [1 , t ]  * Xk-1  +  [  t**2 / 2   ] * a

          [0, 1]               +  [ t               ]

    (Note: some articles use a different variable name for acceleration a as u. )

Let P be the covariance matrix of X along p and u axis. P represents the noise / errors in the prediction. It is a 2x2 matrix. This covariance matrix defines the oval shape and rotation of the Gaussian distribution in the (p, v) space.

Given the covariance matrix P at the k-1 moment, we'd like to calculate the covariance matrix at the next moment k. So given the covariance cov(Xk-1) = Pk-1 , we'd like to find out cov(Xk), which is

    cov(Xk) =  cov(F * Xk-1) 

Co-variance function has the following property: cov(A*X ) = A * cov(X) * A^T . Use this property, thus:

    cov(Xk) =  cov(F * Xk-1)  = F * cov(Xk-1) * F^T 

So, given the covariance matrix at the moment k-1, we can calculate the covariance matrix at moment k. (So, the Gaussian distribution of the next moment can be calculated based on Gaussian distribution of the current moment.)

How do I know my measurement?

In your measurement device, create a few samples and compare them with known distances. Calculate the standard deviation in the data collected from the measurement device. 

Take the product

Now we have two Normal distributions of the next position: one by the linear equation, and another by measurement device. Use the equation µ = µ1 + k * ( µ2 - µ1 ) to take a product of two Normal distributions, as shown in the first section. Since X is in (p, u) space. So the equation should be in vector form, instead of in scalar form. The value of k and mean value are calculated the same, exception k is now calculated based on covariance. Covariances are combined in this way:

K' = ∑1 / ( ∑1  + ∑2 )

∑'  = ∑1 + K' * ∑1

The result looks crazy after plugging in the guessed values based on matrix F, but really they are just the result of the product of two Gaussian distributions.

After Xk is calculated, it will be used as the position to predict in the next round (at k+1 moment). And the calculated ∑' will be used as the covariance matrix for the next round.

Reference:

- https://youtu.be/2-lu3GNbXM8?si=4Xbeiq-LBgTMxbGh&t=750 (voiced in Chinese)

- https://www.youtube.com/watch?v=KD0cH4fTFFU (voiced in Chinese)

Summary on Shusen Wang's video of: Fine-tuning with Softmax Classifier

 In Shushen Wang's video Few-shot learning (3/3), there introduced a simple fine-tuning idea.

1. Softmax classifier

Let x be the raw input, given your feature vector f(x), multiply it with a matrix W plus a bias b. For example, if your classifier generates 3 classes, then the matrix W and b should also have 3 rows. Then take a Softmax.

    p = Softmax(W* f(x) + b)

To initialize matrix W, let each row of the matrix W be the average vector of 1 class to be predicted. Let b to be 0.  W and b are trainable (fine-tuning).

For example, if there are 3 classes, and class 1 has 5 support vectors (from few shot examples), take an average of the 5 support vectors, call it w1, and let that be row 1 in W.

2. Regularization

Since this trick may lead to overfitting, a regularization term is introduced during loss minimization. Since p is a probability, Entropy regularization can be taken on p and seeking smaller entropy becomes part of the loss function.

For example, a prediction p is made for 3 classes, and p = [0.33, 0.33, 0.34]. This prediction may work, but it is pretty bad. So take an entropy at this number:

     entropy = sum( p.map( x => - x * Math.log(x) ) )

     That is - 0.33 * Math.log(0.33) + - 0.33 * Math.log(0.33) +  - 0.34 * Math.log(0.34) = 1.09 in this example.

Include that as part of your loss function (multiply it with a weight) so that training will discourage this kind of the output.

3. Replace Matrix multiplication with Cosine similarity

Say W has 3 classes and thus 3 rows w1, w2, w3. In W* f(x), each row is multiplying f(x) with a dot product. For example w1 * f(x). Instead of a dot product, take a cosine similarity between w1 and f(x).

Basically a dot product first, and divide the determinant of w1 and f(x). (Basically making f(x) and w1 unit vectors before performing the dot product.)

Key, Query, Value Matrices in Masked Self-Attention of Decoder-Only Transformers

   StatQuest uploaded a good video at explaining how a Decorder-Only transformer works. Most of the content talked about how Key, Query, Value Matrices are calculated. It is quite complex. So here I am going to explain it in a more intuitive way (based on my own understanding).

A sentence is first parsed to tokens, and each token has an embedding and its position i in the sentence. The word embedding + the position encoding make a vector for the word at the position i. Nothing special so far.

Now at each token at position i, using this vector (call it word_vector_i), we'd like to encode another vector to represent the context in the sentence so far. This new vector at i should be based on the vector for this word at i and all the previous words from [0, i -1]. To combine these vectors, we are going to take a weighted sum. This is the overall idea.

    vector_with_context (i) =  w1 * value_vector_1 + w2 * value_vector_2 + ... + wi * value_vector_i

But wait, it is not nice to directly use the embedding + positional encoding (word_vector_i) as the value_vector_i. Instead, we will transform it with a matrix (Mv). Mv will be adjustable and learned. So,

    value_vector_i = Mv * word_vector_i

Weight w1 is how similar the 1st word is related to the ith word. Weight w2 is how similar the 2nd word is related to the ith word, etc. To find out how similar the two words are, we are going to apply a dot product on the vector for two words.

But wait, it is not nice to directly use the embedding + positional encoding (word_vector_i), so we again are going to transform word_vector_i with a matrix... Actually, two matrices - one matrix (Mq) for transforming word_vector_i and one matrix (Mk) for transforming word_vector before ith position. 

    query_vector_i = Mq * word_vector_i

    key_vector_1 = Mk * word_vector_1 

    key_vector_2 = Mk * word_vector_2

    ...

    key_vector_(i-1) = Mk * word_vector_(i-1)

Mq and Mk will be adjustable and learned. The weight can be calculated 

    wj = query_vector_i * key_vector_j   

But wait, these weights are not nice. So, we are going to take all the weights and run a softmax to get a better scaled weights (which sum to 1). Applying these weights and value_vector's, vector_with_context(i) is calculated. vector_with_context(i) is called Masked Self-Attention.

To predict the next word at i+1 position, just apply vector_with_context(i) to a fully connected layer to a  result vector representing probability at each word in the dictionary.

But wait, using only masked self-attention (vector_with_context(i) ) isn't nice, we'd like to sum it with embedding and positional encoding (aka word_vector_i as described above). So the prediction of next word is really depending on 3 things. Since we are summing a later vector with an earlier vector, this becomes a residual link in the network.

(Note: since the residual link will sum the masked self-attention and the word embedding, that means their dimensions have to match. This also means Mk, Mq, Mv have to produce the same size. So the size of the Matrix is predetermined.)

Of course, the result vector will apply a softmax to scale probability better.

  - What if it predicted the next word wrong, in my prompt?

      Run your optimizer to train Mk, Mq, Mv and the fully connected layer to make it right.

 - What if I want to generate a reply?

      Repeat the process (without training) to run at every position in your prompt. At the end of the prompt, (at the end-of-sentence token), let the transformer predict the next word. Your transformer is now generating a reply! Keep output the next word and add to the end of the sentence until it outputs the end-of-sentence token.

Short explanation on PEFT: Parameter Efficient Fine Tuning

Many pretrained large language models are out there for us to use. However, they may not be accurate for our purpose. Thus, the model needs fine tuning. 

Since the model is large, the idea is to: make a copy of the existing model, and select a small percentage of trainable features to retrain. With the new copy of the model, train the new copy with your data.

Note that the library does not work with any random model that you created, as the parameter in LoraConfig task_type=TaskType.SEQ_2_SEQ_LM sets an expectation of the model.

LoRa applies the summation with the existing matrices with Low-Rank Matrices to adjust the weights, which is a trick to create a large matrix by adding small amount of parameters

(I explained it earlier in this post.  ) Since only a small percentage of the features are trainable, the training is relatively fast.

This video explains how the LoRA training works internally: 

https://www.coursera.org/learn/generative-ai-with-llms/lecture/NZOVw/peft-techniques-1-lora

Pytorch: How to clear GPU memory

import gc

# del optimizer

# del model

gc.collect()

torch.cuda.empty_cache()

Quick Note: Training with Low-rank Matrices

When training a large matrix M with size WxH parameters is expensive, instead take the matrix into the multiplication of 2 smaller matrices. For example: matrix A is in size of (Wx3) and matrix B is in size of (3xH). And let A * B = M to give back a matrix of WxH dimensions. Since W * 3 + 3 * H < W *H, less amount of parameters are required.

This technique is mentioned in both of the following videos:

 https://www.coursera.org/learn/generative-ai-with-llms/lecture/NZOVw/peft-techniques-1-lora

https://youtu.be/exVPXVFPMDk?t=205

Details in Positional Encoding for Transformer

The Attention is all you need paper mentioned positional encoding without lacking some details. I am going to write my understanding at those details

The formula is the following:

PE(pos,2i) =sin(pos/100002i/dmodel)

PE(pos,2i+1) =cos(pos/100002i/dmodel) 

The paper mentioned that the i is the dimension index of and d_model is dimension of the embedding. If so, given the last i = d_model -1,  2i will be out of the bound. So, that is not the correct explanation.

2i and 2i+ 1 here suggest even and odd dimension indices. At the even dimension indices, apply sine function; at the odd dimension indices, apply cosine function. So i is ranged from [0, to d_model/2) and for each i, it generates 2 dimensions.

Once having the PE (Positional Encoding) value for a position, by the diagram in page 3, it is added to the embedding of the input.

new_embedding[pos, 2i] = embedding[pos, 2i] + PE(pos, 2i) new_embedding[pos, 2i+1] = embedding[pos, 2i+1] + PE(pos, 2i+1)

The embedding variable here is the embedding for each word in a sentence, and pos is the position of the  sentence. (It is a sentence - not the whole dictionary.)

This part of the StatQuest video clearly explained how embedding is calculated.

Key, Query, Value Matrices in Self Attention

The Attention is all you need paper mentioned about an attention function with construction of three matrices Q, K, V without much explanation. Fortunately, this Youtube tutorial on attention explained well (voiced in Chinese). Here is a note that I took from the video.

In self attention, there is only one input, as a list of tokens, each of which is a word expressed as a vector embedding. Call this input X of m elements. Each Xi is the embedding of the ith word. The task to guess the ith word to output, by looking at all words and the i-th word in the input.

Wk, Wq, Wv are the parameter matrices to be learned. Each of them multiplies X to get Q, K, V.

1. It needs to look at all words, which is the Wk matrix multiply X. This matrix is called key matrix as it looks at all keys (words). K = Wk * X

2. It needs to look at the ith word Xi, which is transformed by Q matrix, aka query matrix. qi = Wq * Xi

3. Take the result of K from step 1 and multiply the qi in step 2 and take a softmax. Call this result Ai = Softmax(K.transpose * qi)

4. The context vector at ith location Ai and multiply it with V. Call this result Ci = V * Ai. Since Ai came from step 3 with a softmax , Ci is essentially a weighted sum of V, based on the weight Ai.

5. Take Ci into a Softmax Classifier to get an output word.

Also, Self Attention is a special case of Attention. For self attention, qi is calculated by the ith word in the input Xi. For attention, qi is calculated by looking at the previous output of ith word ( For the very first position, <start> token is considered as the previous output.)

How to run AR.js basic example

Git clone the project of https://github.com/AR-js-org/AR.js

The example has to run from an http server. Opening the example file in the directory won't work. Install nodejs http server

    npm install http-server -g

In your terminal, change directory to the root of AR.js, and run

    http-server

    The server is serving the html files in http://127.0.0.1:8080. Get to http://127.0.0.1:8080/three.js/examples/basic.html in your browser. Allow the page to access camera. The page will start recording you. On your phone, do a Google image search for "hiro marker".  Display the marker on your phone and place in front of the camera. The polygon animation will render on the marker.

AWS Java SDK DynamoDBv2 Scan

AWS Java SDK DynamoDBv2 (com.amazonaws.services.dynamodbv2.document.Table) has a terrible API at performing scan operation. Against common sense, the table.scan(scanSpec) returns a ItemCollection object, which requires the developer to call ItemCollection.iterator() in order to trigger an actual scan. If the ItemCollection.iterator() method is not triggered, the itemCollection.lastLowLevelResult field will be null.

This doesn't work, and will reach Null Pointer Exception:

itemCollection = table.scan(scanSpec) 

System.out.println(itemCollection.lastLowLevelResult.items.size)

This will work - calling of iterator method is required to populate the itemCollection.lastLowLevelResult field.

itemCollection = table.scan(scanSpec)

          List<Item> items = new ArrayList() 

CollectionUtils.addAll(items, itemCollection.iterator()) 

System.out.println(itemCollection.lastLowLevelResult.items.size)

XGBoost Parameter

This is a quick documentation of my understanding of the XGBoost parameters

• max_depth: how deep can one tree grow

• num_rounds : how many trees are in a prediction model

• learning_rate: the weight between applying result (residual value) to the next tree

• alpha: regularization term. (related to pruning trees)

• lambda: regularization term. (related to pruning trees)

• gamma: minimum loss reduction (related to limiting the depth of a tree)

• Reference: 

• https://xgboost.readthedocs.io/en/stable/parameter.html

Java: wait & notify, await & signal, park & unpark

There are several way to stop a thread in Java, to get awaken later. Here are their usages:

wait & notify

Every object has a .wait() and .notify() method. These methods must be called in a synchronized block. 

When a .notify() happened before .wait(), it will not awake the thread.

await & signal 

With ReentrantLock, a condition object can be pulled from the lock, by `lock.newCondition()`. When the lock is locked, .await() These methods needs to be call when the lock is in lock state.

When a .signal() happened before .await(), it will not awake the thread.

LockSupport: park & unpark

Unlike wait & await, LockSupport.park() and LockSupport.unpark(t) and doesn't need to be in a locked / synchronized block. Since LockSupport is permit based, unpark assign a permit to a thread, which can be later used in park . So the order of park and unpark is not strict. Notice that permit doesn't have a counter - it can only be used in 1 park call.

Java Locks: synchronized. ReentrantLock, ReentrantReadWriteLock, StampedLock

synchronized vs. ReentrantLock

Both create critical sections. ReentrantLock is unstructured and can lock and unlock in different methods. ReentrantLock can tryLock with a timeout.

ReentrantLock vs ReentrantReadWriteLock

ReentrantLock creates a critical sections that blocks both read & write. ReentrantReadWriteLock allows readLocks to read together, while blocking by critical sections when write is involved. Note that since readLock can block writeLock, it could result in writeLock starvation when a lot of readLocks appear. WriteLock cannot proceed until all readLocks are unlocked.

ReentrantReadWriteLock vs. StampedLock

ReentrantReadWriteLock is a pessimistic lock, which doesn't read while writer writes, and stops writer when it reads.

StampedLock is an optimistic lock, which reads (by tryOptimisticRead) while allowing write to happen, but also detects write (by validate) - if write happens during the time, simply reads again. 

Getting Started with Haskell - Quick Tutorial

 To install Haskell compiler on MacOS:

brew install ghc

To compile a Haskell file into executable: (the Haskell file must have a main function)

ghc my-haskell-with-main-func.hs

To run without a Haskell file compiling: (the Haskell file will execute without a main function)

ghc -e ':script my-haskell-without-main-func-each-line-is-a-command.hs'

Haskell interactive console:

ghci

To output a string

putStrLn "hello"

To create a Hello World Haskell program

main = putStrLn "hello"

To create a multi-line Haskell program

  main = do

    putStrLn "hello"

    putStrLn "World"

To get stdin to a variable

t <- getLine 

To cast a String value into Int

i = read "123" :: Int

To covert a Int to String

s = show i

To round Float to Int

i = round  1.5

To split a String to a List by space

wordList = words "a b c"

To get item by index from a List 

wordList !! 2

To split a String to a List by new lines

 lineList = lines "hello world\nhi there"

To print a variable

print "hello"

To create a list of integer sequence from 1 to 5

[1..5]

To create a list of integers

[1,2,3] 

To define a lambda function

foo = \x -> x+1

To call a lambda function

foo 1 

To map a List  and apply a lambda function

map (\x -> x+1) [1 .. 2]

To filter a List  and apply a lambda function

filter (\x -> x>0) [1,2,3,0,5,6]

To take unique values of a list

import Data.List

nub [1,2,2,3,3,4]

To sort a List

sort [2,3,1] 

 To compose functions, use .

(map (\x -> x+1) . nub) [1,2,2,2,2]

To pipe functions from right to left without compose, use $

map (\x -> x+1) $ nub [1,2,2,2,2]

To flatten / merge multiple Lists into one List

concat [[1,2],[3,4]]

To join a List of String to one String with a delimiter

intercalate " " ["a", "b", "c"]  

To reduce, use foldr

foldr (\x s -> s+x) 100 [1,2,3]

foldr is kind of slow. Use foldl

foldl (\s v -> s+v) 100 [1,2,3] 

To sum numbers in a List

sum [1,2,3] 

To divide a List into a List of groups (Lists), each of which collects the repeated items in sequence:

groupBy (==) "aabbcccdddde" 

Write a function that returns constant value

f = (const 1)

f 100

To get combination of of a list with itself (Note: a String is a List)

        mapM (const "ABC") [1,1] 

To comment

-- This is a comment

To take power of a number

x ** 2     -- will result in Float value

x ^ 2       -- will result in Int value

To take absolute value

abs x

To take modulo of two values (% doesn't work)

mod 5 3 

To perform integer division

div 5 3 

To compare values with not equals (!= doesn't work)

1 /= x 

To get the max value in a List of values

maximum [1,2,3] 

To concat two Strings

"Hello" ++ "World"

To concat two Lists

[1,2,3] ++ [4,5,6]

To reverse a List

reverse [1,2,3] 

To take a for loop (

mapM_ (\i -> do {

    print $ "hello" ++ show i

})  [1.. 5]

-- Note: what do {} is used, remember to add ; at the end of each line, except for the last line.

-- Note: use mapM_ for side effect, and expect mapM_ to return no value.

To use ternary operator

x = 2

y = if x > 1 then "YES" else "NO" 

To define a variable in multi-line program

let { x = 2 }; 

To create a pair and get its left and right value, use a tuple:

 a = (1,2)

v1 = fst a

v2 = snd a

To zip two Lists into a List of pairs (tuples)

zip [1,2,3] ['a','b','c'] 

To define a lambda function that takes a tuple as input parameter:

(\(a,b) -> a+b) (1,2) 

Can I transpose a matrix? Yes, you can

import Data.List 

transpose [[1,2],[3,4]] 

Take length of a List

length [1,2,3] 

Take the first few from a List

take 1 [1,2,3]

Remove the first few from a List

drop 1 [1,2,3]

Drop the last one from a List

init [1,2,3,4,5]

Get the first value in a List

head [1,2,3] 

Get the last value in a List

last [1,2,3] 

Traverse a List until it doesn't match a condition

takeWhile (\x -> x > 0) [1,2,3,0,5,6] 

To get a String (List) of repeated values of a certain length

take 10 $ repeat '_' 

To define a recursive function: (you can define what a function return when a certain value is received at the parameter.)

f 0 = 0

f 1 = 0

f 2 = 1

f n = f (n-1) + f (n-2)

 To define a function f with multiple scenarios by conditions

f v

 | v > 0 = ">0"

 | v < 0 = "<0"

 | otherwise = "0"

To dynamic programming with recursion, see a tutorial on Data.Function.Memoize for fibonacci.

For example https://gist.github.com/yuhanz/e1c6793d3e8cb39fac0fa0ab9685235a

Quick Tutorial: What is XML External Entities (XXE) Attack?

Vulnerable Scenario: your service takes in XML as input, and respond the content from the input (usually on error to indicate some parameter value).

Because XML has a DOCTYPE for variable replacement, you can easily define a variable to be replaced in the XML. For example, to define a variable myVar = "hello"

    <!DOCTYPE Query [ <!ENTITY myVar "hello" > ]>

This can be further extended to read a file on your disk for the content and assign it to the variable:

    <!DOCTYPE MySearchKeyword [ <!ENTITY myVar SYSTEM "file:///etc/passwd" > ]>

The attack: combine file reading with your XML input:

<?xml version='1.0' encoding='ISO-8859-1'?><!DOCTYPE Query [ <!ENTITY myVar SYSTEM "file:///etc/passwd" > ]> <Search>&myVar;</Search>

After our server will take the content inside <Search> to search (which is your passwd file), and it will respond with the file content to the client.

Solution:

 - Disable DTD feature in XML.

Quick Tutorial: What is Server-Side Request Forgery (SSRF)?

Vulnerable Scenario: when your app allows a user to send a URL to curl (or fetch, etc), potentially the user can curl a file on your server with:

curl file:///etc/passwd

So to improve the security against this, apply a check on the URL schema (not to accept with URL starting with file://)